The Necklace Expenditure

All submissions for this problem are available.
Sheldon is excited as it is Amy's birthday the day after. So he decided to give her a necklace but he is totally confused on how the necklace should look like. How many different colored beads should it have, so in order to clear his doubt he designed a mathematical model of the necklace. In his mathematical model, He first assumed that the necklace contains 'N' beads with a period of 'K'. Where period of a necklace can be defined as 'From any bead if we choose a bead that is 'K' beads away in either direction we get the same color bead'.
For e.g. 1 1 2 2 6 2 1 1 5 3 2 4
The first necklace has two different coloured beads with period of 2, 4, and 6. whereas the second necklace has six different coloured beads, with period of 6.
So for a particular period we will have a maximum number of different coloured beads. i.e. in the above example both necklace 1 and necklace 2 has period of 6 but we have 2 and 6 number of differently coloured beads in these necklaces. so for length 6 and period 6 maximum number of differently coloured beads in the necklace is 6.
But as Sheldon was not aware of the period of the necklace so he chose 'K' randomly from 1 to 'N', and wants to find the expected maximum number of different coloured beads in the necklace.
Input
First line contains the no of test cases 'T'.
Then 'T' lines follow each containing one integer 'N'.
Output
'T' lines corresponding to each test case which contain the expected maximum number of different coloured beads that can be inside the necklace, if the number of beads in the necklace is 'N', and its period is randomly chosen from 1 to 'N' correct upto 3 decimal places.
Limits
T <= 200000
1 <= N <= 1000000
Example
Input: 2 6 2 Output: 2.500 1.500
Test case Explanation
Test case 1:
For 6 if the period of the necklace is
1 the maximum number of different coloured beads it can have is 1
2 the maximum number of different coloured beads it can have is 2
3 the maximum number of different coloured beads it can have is 3
4 the maximum number of different coloured beads it can have is 2
5 the maximum number of different coloured beads it can have is 1
6 the maximum number of different coloured beads it can have is 6
hence answer is (1 + 2 + 3 + 2 + 1 + 6) / 6 = 2.50
Test case 2:
For 2 if the period of the necklace is
1 the maximum number of different coloured beads it can have is 1
2 the maximum number of different coloured beads it can have is 2
hence answer is (1 + 2) / 2 = 1.50
Author:  udayrocks2k8 
Tags  udayrocks2k8 
Date Added:  15102011 
Time Limit:  0.163934 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 