SP6981 RNDORDER - The Least Number

You are given n symbols a $ _{1} $ , a $ _{2} $ ,..., a $ _{n} $ . You are told that there is a total ordering of the symbols. That is, there is a permutation \[P1, P2,..., Pn\] of \[1,2,...,n\] such that a $ _{P1} $ < a $ _{P2} $ a $ _{j} $ . If Compare\[a $ _{i} $ , a $ _{j} $ \] = -1, it means a $ _{i} $ < a $ _{j} $ . - Compare is consistent. Suppose, that you queried \[a $ _{2} $ , a $ _{6} $ \] and it was already established \[a $ _{2} $ < a $ _{6} $ \] (because for example a $ _{2} $ < a $ _{5} $ and a $ _{5} $ < a $ _{6} $ - since both of these comparisons happen earlier), then \[a $ _{2} $ , a $ _{6} $ \] returns -1. - If no relationship is known between a $ _{i} $ and a $ _{j} $ , Compare\[a $ _{i} $ , a $ _{j} $ \] = 1 with probablity 1/2 and -1 with probability 1/2 Your task is to output the probability that a $ _{1} $ is the smallest element of the final ordering so obtained.

First line contains T, the number of test cases Each of the next T lines contains one number each, **n**(1

Output T lines in total, one per test case: Probability that a $ _{1} $ is indeed the smallest element at the end of the comparisons. Your output will be judged correct if it differs by no more than 10 $ ^{-9} $ to the reference answer.