Open Contest 2007

We are trying to develop the electrical power infrastructure in the small country of Byteland. For this purpose not far from each city we have built a nuclear power plant (NPP). We have also connected the nearest house to this NPP with a cable. The goal of this project is to connect all houses of each city to the source of electricity. Each house already connected to electricity become a source of electricity. Since there is a severe shortage of electrical cable, the total length of the electricity network should be kept as small as possible. In some places we can set up transformer/splitter boxes to which we can potentially connect several cables; all their endpoints are then considered connected.

Input

t – the number of cities; then follows the description of each of t cities. [t <= 50]
The description of each city begins with N - the number of houses in the city [3 <= N <= 3000]. Then exactly N lines follow, with two real numbers: x, y in each, representing the coordinates of a house. [0.0 <= x, y <= 10000.0]

Output

For each test case you must output a connected electrical net, e.g. all houses must be connected with each other, directly, through other houses or through transformers. For each test output integer M [0 <= M <= N] - the number of required transformers. On each of following M lines output the coordinates of the transformers x, y [0.0 <= x, y <= 10000.0]. Next output the number K which is equal to the number of required cables [N+M-1 <= K <= (M+N)*(M+N-1)/2]. On the following K lines output two integers i, j - indexes of houses or transformers. Indexes for houses begins with 0 and end with N-1, indexes for transformers begin with N and end with N+M-1.

Score

The score for the problem is given as: total_score = (200+time)*(score_1+score_2+...score_t)/200. In the above formula, score_i is equal to the length of the electrical cable used for electrification of the ith city, and time is the runtime of your solution.

Example

Input:
1
4
1.0 1.0
1.0 11.0
11.0 1.0
11.0 11.0

Output:
1
6.0 6.0
4
0 4
1 4
2 4
4 3

Score:

Suppose that the solution ran for 10 seconds. The length of the cable is score_1 = 20*sqrt(2). In this case number of points awarded to the program will be equal to 29.698485.