Expectation
Eric has constructed an easy scheme for generating random integer numbers. His scheme inputs an integer n and generates evenly distributed random integer value between 0 and (n − 1) inclusive. Forexample, if n = 3, the scheme generates 0, 1 or 2, each with probability 1/3.
Now Eric is planning to construct more complicated schemes. The first one will consist of two independent random generators with their outputs forwarded to his favorite XOR gate, which does bitwise exclusive orwith its two inputs.
Eric's friend Nick studies math. Nick said that the scheme is very interesting, and the most interestingthing is the expectation of the result. Now they both think how to calculate the expectation. Could youhelp them?
Remember that the expectation of the random variable is its average value. For a variable ξ with nonnegativeinteger values it can be calculated as
where p[i] is the probability of ξ being equal to i.
Input
The first line contains the number of cases k (1 ≤ k ≤ 1000) to solve. Each case consists ofa single integer n (1 ≤ n ≤ 10^9) on a separate line.
Output
For each case output the expected value of the new Eric's scheme with at least two digits after the decimalpoint. Output each result on a separate line.