H :: Hitler’s Board

Time Limit: 7 Seconds    Memory Limit: 32768 KB

Adolf Hitler uses a large board-map in the center of “control and command” in his house for managing the resources in the wars. He has encountered a problem now. Let’s listen to him:

Hitler: “I have a big board with some nails on it. Consider all distinct pairs of the nails. Each pair can be connected by a string directly. I desired to connect some pairs with the minimum usage of string such that we have a direct or indirect connection between each pair of the nails. Anyway, I did not it yet.

If two nails are connected by a string, it is hard to open it. My wife called me (by phone) and told me some bad news. My son (in my absence) has connected two nails to each other and it means that the minimum usage of string may change. I do not know which pairs are connected now. Corresponding to each pair, we have an extra usage of string. How many of the pairs have the minimum usage of string and what is the expected (Average) extra usage of string.”

Input

The first line of the input contains an integer T≤100 denoting the number of test cases. Each test case starts with an integer 2≤N≤ 5,000 denoting the number of nails followed by N lines each containing a pair of integers x and y denoting the position of a nail on the board 0≤x,y<5,000.

Output

For each test-case, output in a single line the number of pairs with the minimum usage of string followed by a space and then the expected (average) extra usage of string with exactly four digits after floating point.

Sample Input

2
4
0 0
1 0
0 1
1 1
8
0 0
0 8
8 0
8 8
2 2
6 2
6 6
2 6

Sample Output

4 0.1381
8 2.5171

Submit

Source: 12th Iran Nationwide Internet Contest IV