Bridge

Recently a large typhoon swept away every bridge between the islands. What is done is done, and now the road network has to be rebuilt. As an emergency recovery plan, the government decided to build bridges so that people can travel between any pair of islands without getting wet. In other words, all islands must end up connected to one another through bridges.

Building a bridge of length $x$ costs $x^2$. The length of a bridge between two islands is the shortest straight-line distance between them, that is, the Euclidean distance between the two closest points of the two rectangles. You may build as many bridges as you like; connect all islands so that every island is reachable from every other one, while keeping the total cost as small as possible.

Thanks to land reclamation, every island is a rectangle whose sides are parallel to the coordinate axes. Given the positions and shapes of the islands, compute the minimum total cost of connecting them all.

Figure 1. An example of connecting islands with bridges.

The first line contains an integer $T$ with $1 \le T \le 20$, the number of test cases.

Each test case begins with a line containing an integer $N$ with $2 \le N \le 5000$, the number of islands. Each of the next $N$ lines contains four integers $x$, $y$, $w$, $h$ with $0 \le x, y, w, h \le 10000$, where $(x, y)$ is the upper-left corner of an island and $w$ and $h$ are its width and height. The island covers every point $(p, q)$ with $x \le p \le x + w$ and $y - h \le q \le y$.

For each test case, print a single line with one integer: the minimum total cost of connecting all islands.