AND gates and OR gates are basic components used in building digital circuits. Both gates have two input lines and one output line. The output of an AND gate is 1 if both inputs are 1, otherwise the output is 0. The output of an OR gate is 1 if at least one input is 1, otherwise the output is 0.

You are given a digital circuit composed of only AND and OR gates where one node (gate or input) is specially designated as the output. Furthermore, for any gate G and any input node I, at most one of the inputs to G depends on the value of node I.

Now consider the following random experiment. Fix some probability p in [0,1] and set each input bit to 1 independently at random with probability p (and to 0 with probability 1-p). The output is then 1 with some probability that depends on p. You wonder what value of p causes the circuit to output a 1 with probability 1/2.

-----Input-----

The first line indicates the number of test cases to follow (about 100).

Each test case begins with a single line containing a single integer n with 1 ≤ n ≤ 100 indicating the number of nodes (inputs and gates) in the circuit. Following this, n lines follow where the i'th line describes the i'th node. If the node is an input, the line simply consists of the integer 0. Otherwise, if the node is an OR gate then the line begins with a 1 and if the node is an AND gate then the line begins with a 2. In either case, two more integers a,b follow, both less than i, which indicate that the outputs from both a and b are used as the two input to gate i.

As stated before, the circuit will be such that no gate has both of its inputs depending on the value of a common input node.

Test cases are separated by a blank line including a blank line preceding the first test case.


-----Output-----

For each test case you are to output a single line containing the value p for which the output of node n is 1 with probability exactly 1/2 if the inputs are independently and randomly set to value 1 with probability p. The value p should be printed with exactly 5 digits after the decimal.


-----Example-----
Input:

4

1
0

3
0
0
1 1 2

3
0
0
2 1 2

5
0
0
0
2 1 2
1 3 4

Output:

0.50000
0.29289
0.70711
0.40303

-----Temporary Stuff-----

A horizontal rule follows.

***

Here's a definition list (with `definitionLists` option):

apples
: Good for making applesauce.
oranges
: Citrus!
tomatoes
: There's no "e" in tomatoe.

#PRACTICE
- This must be done
[http:codechef.com/users/dpraveen](http:codechef.com/users/dpraveen)

(0.8944272−0.44721360.4472136−0.8944272)(10005)(0.89442720.4472136−0.4472136−0.8944272)(10005)
\left(\begin{array}{cc} 
0.8944272 & 0.4472136\\
-0.4472136 & -0.8944272
\end{array}\right)
\left(\begin{array}{cc} 
10 & 0\\ 
0 & 5
\end{array}\right)

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nclass node:\n\tdef __init__(self,a,b=0,c=0):\n\t\tself.val=a\n\t\tself.a=b\n\t\tself.b=c\n\narr=[]\n\ndef finder(node,val):\n\tif(arr[node].val==0):\n\t\treturn val\n\telse:\n\t\ta=finder(arr[node].a,val)\n\t\tb=finder(arr[node].b,val)\n\t\tif(arr[node].val==1):\n\t\t\treturn a+b-a*b\n\t\telse:\n\t\t\treturn a*b\n\nt=int(input())\nwhile(t>0):\n\tx=input()\n\tn=int(input())\n\tarr.append(node(0))\n\tfor i in range(0,n):\n\t\tvals=input().split()\n\t\tsz=len(vals)\n\t\tfor i in range(0,sz):\n\t\t\tvals[i]=int(vals[i])\n\t\tif(vals[0]==0):\n\t\t\tnext=node(0)\n\t\t\tarr.append(next)\n\t\telse:\n\t\t\tnext=node(vals[0],vals[1],vals[2])\n\t\t\tarr.append(next)\n\tlower=0.0\n\thigher=1.0\n\teps=1e-9\n\twhile((higher-lower)>eps):\n\t\tmid=(higher+lower)/2.0 \n\t\tif(finder(n,mid)>0.5):\n\t\t\thigher=mid\n\t\telse:\n\t\t\tlower=mid\n\tprint("%.5f" %(higher))\n\tarr=[]\n\t# print(higher)\n\tt-=1'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 16525