F. Expected Runtime
time limit per test
3.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Rami was playing with the following algorithm. He chooses a positive integer $$$n\in\mathbb{N}^*$$$

He begins with $$$R= 1$$$ and $$$k=0$$$ and while $$$R\bmod n\ne 0,$$$ he:

  1. Chooses a random number $$$a\in\{0,\dots,n-1\}$$$
  2. He sets $$$R\leftarrow R\times a$$$
  3. He increments $$$k:k\leftarrow k+1$$$

As $$$k$$$ denotes the number of iterations on the loop, he wants to know the expected value of $$$k$$$.

Input
  • The first line contains an integer $$$1\le T \le 10^3:$$$ the number of test cases.
  • Each test case is represented by a line containing a single integer $$$1\le n \le 10^6$$$
Output

For each test case, output a single real $$$k:$$$ the expected runtime of the algorithm.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{max(1,|b|)} \le 10^{-6}$$$.

Example
Input
6
2
3
10
25
100
1024
Output
2.000000
3.000000
5.333333
9.000000
9.296296
11.000000