Description

Peppa and George are playing a game.

Peppa writes the numbers $\{1,2,\cdots,n\}$ on the blackboard. Each round, they will choose a number $x$ that is currently on the blackboard uniformly at random, and then delete all positive integer powers of $x$.

Formally, given the sequence $\{1,2,\cdots,n\}$, each time they uniformly select $1$ number $x$ that exists in the sequence, and delete all numbers of the form $\{x^k,k \in Z^{+}\}$.

They played for a whole afternoon, but the game still did not end, so they want to know: after how many rounds is the game expected to end.

If the absolute error between your answer and the correct answer is within $10^{-4}$, then it will be judged as correct.

Input Format

The first line contains $1$ positive integer $t$, meaning Peppa and George plan to play $t$ games.

Then follow $t$ lines, each with $1$ positive integer $n$, meaning Peppa wrote the numbers $\{1,2,\cdots,n\}$ on the blackboard and will start the game.

Output Format

Output a total of $t$ lines, each containing $1$ decimal number, representing the answer. Keep the decimals.

If the absolute error between your answer and the correct answer is within $10^{-4}$, then it will be judged as correct.

5
4
8
16
32
100

3.50000000
7.00000000
13.83333333
28.33333333
93.41666667

Hint

For $n=4$,

If the deletion order is $\{1,2,3\},\{3,2,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{1}=\frac{1}{12}$.

If the deletion order is $\{1,3,2\},\{3,1,2\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2}=\frac{1}{24}$.

If the deletion order is $\{2,1,3\},\{2,3,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{8}$.

For the remaining $12$ sequences that delete $4$ times, the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{24}$.

It is easy to see that the answer is $\frac{2 \times 3}{12} + \frac{2 \times 3}{24}+\frac{2 \times 3}{8} + \frac{12 \times 4}{24}=\frac{7}{2}=3.50000$.

Constraints

For $20\%$ of the testdata, $n \leq 10$.

For $60\%$ of the testdata, $n \leq 10^5$.

For $100\%$ of the testdata, $n \leq 10^9,t \leq 100$.

A Friendly Reminder from the Problem Setter

For C++ users, for positive integers $n,k$, if you want to compute $\sqrt[k] n$, please try not to use the built-in C++ function $\operatorname{pow}$, in order to avoid possible unnecessary precision errors.

Input Format

The first line contains $1$ positive integer $t$, meaning Peppa and George plan to play $t$ games.

Then follow $t$ lines, each with $1$ positive integer $n$, meaning Peppa wrote the numbers $\{1,2,\cdots,n\}$ on the blackboard and will start the game.

Output Format

Output a total of $t$ lines, each containing $1$ decimal number, representing the answer. Keep the decimals.

If the absolute error between your answer and the correct answer is within $10^{-4}$, then it will be judged as correct.

Hint

For $n=4$,

If the deletion order is $\{1,2,3\},\{3,2,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{1}=\frac{1}{12}$.

If the deletion order is $\{1,3,2\},\{3,1,2\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2}=\frac{1}{24}$.

If the deletion order is $\{2,1,3\},\{2,3,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{8}$.

For the remaining $12$ sequences that delete $4$ times, the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{24}$.

It is easy to see that the answer is $\frac{2 \times 3}{12} + \frac{2 \times 3}{24}+\frac{2 \times 3}{8} + \frac{12 \times 4}{24}=\frac{7}{2}=3.50000$

Translated by ChatGPT 5