URI Online Judge | 1625

Robocopy

By Enrique Finn, Universidade Federal de Uberlândia BR Brazil

Timelimit: 7

Robocopy are drones that once activated they copy rotational motion each other. When a drone is activated along with others, they work together as if they were one.

Daniel recently bought a factory of robocopy. A robotic arm places each robocopy randomly in an area, thus forming a set of robocopy. Each set may be composed of different numbers of robocopy. And to test them, they are activated. The activated robocopy must pass a treadmill for later deactivated and stored. Several sets of rodocopy can go through the same treadmill. The treadmill width should always be the lowest possible, but that it contains all the sets.

As Daniel is an inexperienced entrepreneur, did not do a proper planning and then had to hire additional staff to manually check which size mat he has to configure to support different sets of robocopy. Of course, this process is very costly and time consuming.

To reduce costs and increase efficiency, Daniel hired you to calculate automatically, which the smaller track width for all sets robocopy can be stored properly.

Figure 1.


Figure 2.


In Figure 1, for example, 3 robocopy were activated by the machine(A, B and C) and the smallest distance is a = 2, among BC. When the machine does the other set of robocopy (A, B, C and D) of Figure 2, the smallest distance is AB or DC, b = 3, and in this case the set of robocopy must be rotated 90 degrees to pass over the treadmill which has size 3. So, if these sets were passing by the treadmill, this would have to have a minimum width of 3.

Input

The input consists of several test cases.

The first line consists of an integer N (1 ≤ N ≤ 10000) that represents the number of test cases.

Each test case consists of an integer C (1 ≤ C ≤ 100) indicating the number of sets of robocopy manufactured. Each set consists of an integer c (1 ≤ c ≤ 10 000) representing the number of robocopy of the set, followed by c rows of integers indicating the coordinate -100000 ≤ (x, y) ≤ 100 000 of each one robocopy of the in C.

Output

In each row should be printed the size of the smallest treadmill to produce all sets of robocopy with accuracy of 10 decimal places.

Sample Input Sample Output

1

2
4
1 4
1 1
5 1
5 4
3
1 1

1 3
3 3

3.0000000000