Grammy and Oscar bought a big cake. They like it very much, so dividing the cake becomes difficult. In order to divide the cake in a relatively fair way, they decided to play a game to earn more part of the cake for themselves.

The game consists of two phases.

For phase , Grammy and Oscar will play on a tree rooted at vertex . Each edge of the tree has a number or . Initially, there is a horse on the root.
They take turns moving the horse, with Grammy moving first. At each turn, suppose the horse is at vertex , the player must select some child of and move the horse to that child of . Phase ends when has no children. As a result of phase , we will get a string formed by concatenating the numbers on edges the horse has passed by. Note that consists of only and .

For phase , Grammy and Oscar will play on the string they obtained in phase . Let be the length of . Firstly, Oscar will divide the cake into parts (some parts can be empty). Then steps follow. At the -th step, if the -th character of is , Grammy will choose one part and get it; otherwise, Oscar will choose one part and get it.

Both of them hope to maximize the cake they get, and they both play optimally. Please calculate the fraction of cake Grammy gets.

There are multiple test cases. The first line of the input contains an integer  () indicating the number of test cases. For each test case:

The first line contains one integer  (), indicating the size of the rooted tree in phase .

For the following  lines, the -th line contains three integers  () describing an edge connecting  and  with number .

It is guaranteed that the sum of  over all test cases will not exceed .

For each test case:

Output one line containing one real number indicating the fraction of cake Grammy gets in the game, assuming both players play optimally.

Your answer is considered correct if its absolute or relative error does not exceed .

Formally, let your answer be , and the jury's answer be . Your answer is accepted if and only if .

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

1.000000000000
0.500000000000
0.000000000000