Duck plays the role of God in a game. In the game world, there are N villages, each occupying an axis-aligned rectangular piece of land. He wants to unite the people, and one of the ways to do so is by connecting all the villages with roads so that everyone can meet. A road is a straight line segment of arbitrary length.

To maintain the consistency of the landscape, the roads must also be axis-aligned, be perpendicular to a village's border, and be connected to any point on the border except its vertices at the two ends. Note that if two villages overlap, the people there can already meet. Two villages touch each other by sharing a border or a vertex are not considered to "overlap".

Find the minimum number of roads required to connect all the villages.

Input

The first line is the number of test cases T. (1 ≤ T ≤ 30)

For each test case, it starts with one integer N. (1 ≤ N ≤ 5000)

Following N lines, each consisting of four integers X₁ Y₁ X₂ Y₂ representing the lower-left coordinates and the upper-right coordinates of the i-th village's border. (0 ≤ X₁, Y₁, X₂, Y₂ ≤ 10⁹ and X₁ < X₂ and Y₁ < Y₂)

Output

Output an integer indicating the minimum number of roads required to connect all the villages.

Example

Input:
2
9
6 9 8 10
8 10 9 11
9 10 10 11
4 5 6 7
9 3 10 4
8 3 9 4
4 7 6 9
6 4 8 5
0 6 5 8

10
6 0 11 1
9 1 11 6
1 9 3 10
0 6 2 8
2 1 6 6
2 3 4 6
3 2 8 4
7 5 10 8
5 7 11 8
11 8 12 9

Output:
8
6

Explanation

Case 1	Case 2