IIST is thinking of acquiring some land nearby to build its new state of the art labs. The land it has chosen incidentaly has some abandoned college buildings which IIST wants to use. The administration decide the value of the building based on the amount of work that has to be done to get it in shape (lower amount of work, higher value). The security experts want to tear down some of the buildings and use the bricks to build a boundary wall.

The director has chosen you to write a program which determines the buildings which needs to be demolished to maximise the value while fulfilling the above criterion.

Input Format:

The first line contains the number of test cases, T.

The next T cases contains information about hypothetical plots.

Each test case starts with a single integer n, 2 ≤ n ≤ 15, the number of abandoned buildings in the plot. The buildings are identified by consecutive integers 1 to n. Each of the subsequent lines contains 4 integers x_i , y_i , v_i , l_i that describe a single building. (x_i, y_i) is the position of the building in the plane, v_i is its value, and l_i is the length of boundary wall that can be built using the bricks from the building. v_i and l_i are between 0 and 10,000.

Output Format:

For each test case, compute a subset of the buildings such that, using the bricks from the buildings from that subset, the remaining buildings can be enclosed in a single boundary. Find the subset with a minimum value. If more than one such minimum-value subset exists, choose one with the smallest number of buildings.

Display, as shown below, the identity of each building to be demolished, and the length of the excess boundary (accurate to two fractional digits).

Sample Input:

2

6

0 0 8 3

1 4 3 2

2 1 7 1

4 1 2 3

3 5 4 6

2 3 9 8

3

3 0 10 2

5 5 20 25

7 -3 30 32

Sample Output:

2 4 5

3.16

2

15.00

见题面

见题面