Problem: Little Elephant from the Zoo of Lviv hates exams. Since Little Elephant lives in Ukraine, he is going to take exams called 'ZNO'. Help him.
There will be n tickets on the table. Each ticket has a number written on it. The i-th ticket can be numbered Ai with probability Pi percent and with probability 100-Pi percent it can be numbered Bi. It can not have any other number. A numbering of tickets on the table is correct if and only if all tickets have distinct ticket numbers.
Help Little Elephant find the probability that the numbering will be correct.

Input
The first line of the input contains a single integer T - the number of test cases. T test cases follow. The first line of each test case contains a single integer n - the number of tickets on the table. n lines will follow. Each of these lines contains three integers: Pi,  Ai and Bi.

Output
Output T lines, each containing a single real number - answer for the corresponding test case. Rounding errors less than 10^-6 will be ignored.


Constraints

1 <= T <= 10

1 <= n <= 50

1 <= Ai, Bi <= 16

0 <= Pi <= 100


Example

Input:
2
2
50 1 2
50 2 1
3
100 1 3
47 2 1
74 3 2

Output:
0.500000000
0.347800000

Solution (in PYTHON):

Solution:
rounds = int(raw_input())

A,B,P = [],[],[]

def main():
    for _ in range(rounds):
        tickets = int(raw_input())
        global A, B, P
        A,B,P = [],[],[]

        for _ in range(tickets):
            p, a, b = raw_input().split(" ")
            P.append(int(p))
            A.append(int(a))
            B.append(int(b))
        # compute probability of lossing game
        # just iterate each tickets, sum up lossing prob
        # every tickets have two option, make this is binary tree
        print win_prob([], 0)
def win_prob(path, i):
    if i >= len(A):
        return 1
    
    loss_a = A[i] in path
    loss_b = B[i] in path
    p1, p2 = 0, 0
    if not loss_a:
        path.append(A[i])
        p1 = P[i] / 100.0 * win_prob(path, i + 1)
        path.pop()
    if not loss_b:
        path.append(B[i])
        p2 = (100 - P[i]) / 100.0 * win_prob(path, i + 1)
        path.pop()
    return p1 + p2

if __name__ == '__main__':
    main()