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

Explanation

For N = 2, you can have the following two permutations: [1, 2] and [2, 1].

In the first case the if block gets executed 2 times, and in the second case the if block gets executed 1 time. So the expected value is (2 + 1) / 2 = 1.5


hide comments
ishaan: 2014-01-11 13:33:46

Is this trick some pre-defined formula for solving this question?
I am unable to come up with a formula that fits with all cases.
Edit:Got the pattern

Last edit: 2014-01-11 13:56:19
Tarun Garg: 2013-12-28 11:24:56

Think like a lazy man....:D

Bhavik: 2013-12-26 17:58:12

good question :)

Nick: 2013-12-25 06:46:14

Yes, there's a pattern behind this. You can try.. Btw, thanks @[ _BaDsHah_ ]

I print the answer in single decimal got WA, but normal decimal AC.

Last edit: 2013-12-25 06:50:49
Akhilesh Anandh: 2013-11-09 21:59:19

Really good problem.. finally discovered the trick :D

Alien: 2013-07-02 11:33:55

agreed hasil

Last edit: 2013-07-02 11:37:04
Hasil Sharma: 2013-07-02 11:23:37

KingAditya , can't agree more you only need to know the trick nothing else

DOT: 2013-06-21 10:48:43

Some more test cases, please.

Alien: 2013-06-21 10:28:09

EASY PROB,if you know the trick

Chandan Mittal: 2013-06-01 18:25:22

what will be the o/p for
2

3
4


Added by:Aman Gupta
Date:2013-04-20
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own