You are given n symbols a₁, a₂,..., 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_Pn. You are trying to figure out the order by doing comparisons. The process you follow for determining the order is as follows:

• Compare [a₁, a₂]
• Compare [a₂, a₃], [a₁, a₃] 
• Compare [a₃, a₄], [a₂, a₄], [a₁, a₄]
• ....
• ....
• Compare [a_n-1,a_n], [a_n-2,a_n],..., [a₁, a_n]

Note that you compare in the order specified. That is you compare [a₂, a₃], then and only then do you compare [a₁, a₃].

Definition of Compare[a_i, a_j] (i < j)

• If Compare [a_i, a_j] = 1, it means a_i > a_j. If Compare[a_i, a_j] = -1, it means a_i < a_j. 
• Compare is consistent. Suppose, that you queried [a₂, a₆] and it was already established [a₂ < a₆] (because for example a₂ < a₅ and a₅ < a₆ - since both of these comparisons happen earlier), then [a₂, a₆] 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₁ is the smallest element of the final ordering so obtained.

Input

First line contains T, the number of test cases

Each of the next T lines contains one number each, n(1 <= n <= 1000). 

Output

Output T lines in total, one per test case: Probability that a₁ 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.

Example

Input:

3

1

2

3
Output:

1

0.500

0.3750000

Explanation:

n = 1 is trivial

For n = 2, only comparison is [a1, a2]. a1 is lower with probability 1/2.

For n = 3, a1 is not the least element if either (a1 > a2) or (a1 < a2 and a3 < a2 and a3 < a1). 

So, probability that a1 is not the least element = 1/2 + 1/8 = 5/8. Probability that a1 is the least = 3/8 = 0.375.