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 probability 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 [a₁, a₂]. a1 is lower with probability 1/2.

For n = 3, a1 is not the least element if either (a₁ > a₂) or (a₁ < a₂ and a₃ < a₂ and a₃ < a₁).

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