LOOPEXP - Loop Expectation

Consider the following pseudo-code

int a[1..N];

int max = -1;

for i = 1..N:

if(a[i] > max)

max = a[i];

Your task is to calculate the expected number of times the 'if' block of the above pseudo-code executes. The array 'a' is a random permutation of numbers from 1..N chosen uniformly at random.

Input

First line contains t, the number of test cases. t lines follow, each containing N, the number of elements in the array.

1<= t <= 100

1<= n <=100,000

Output

For each test case, output a single decimal. Your answer should be within 10^-6 of the correct answer.

Example

Input:
1
2

Output:

1.5
Explaination :
for N=2, you can have the following two permutations: [1,2]  and [2,1] .
for the first case the if block gets executed 2 times and for the second one the if block gets executed 1 time. So the expected
value is (3)/2 = 1.5

 < Previous 1 2 3 Next > nadstratosfer: 2017-09-28 04:49:55 Found the pattern quickly, spent 1.5h trying to reduce the formula to something computable. Failed, tried what I thought was bruteforce, expected TLE - got AC! Not a good time though so decided to precompute, expected WA due to floats - got AC and best time in Python! Rare case of positive WTF. sfialok98: 2017-06-26 16:38:07 Nice problem.. Solved using DP and Big Numbers.... sonudoo: 2017-02-08 13:40:35 Enjoyed deriving the formulae :) aditya1997: 2016-08-26 08:51:25 use double instead of float. ps: u can print as many digits after . but the answer must be in range of 10^-6 of the official answers square1001: 2016-08-16 04:49:55 Easy. Find the logic. Archit Jain: 2014-08-20 17:01:18 enjoyed solving it Anubhav Balodhi : 2014-08-13 20:45:49 Once you work on paper, the problem is simpler... SanchitK: 2014-03-24 15:30:14 someone please tell the answer for n=6 785227: 2014-03-20 13:42:46 I found the pattern.. But what does 10^-6 of the correct answer mean ?? I think i am getting WA because of this Phoenix007: 2014-02-01 11:18:25 Very nice problem.. :)