#575 Pillow CPU

Loading problem...

Preparing the statement, recent submissions, and submit form.

#575 Pillow CPU

Authors: pillowprism

Time limit: 4000 ms
Python time limit: 8000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

Pillow CPU repeatedly transforms a positive integer $N$ by the following process.

If the current value is $N=1$ , terminate the process.
Choose an integer $x$ uniformly at random from $2$ through $N$ . This step takes $1$ second.
If $N$ is divisible by $x$ , replace $N$ by $N/x$ . Otherwise, leave $N$ unchanged.
Return to step $1$ .

Given the initial integer $N$ , compute the expected time until the process terminates. The elapsed time depends only on the number of times step $2$ is executed.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the expected time until the process terminates, rounded to exactly two digits after the decimal point.

Constraints

$1 \le T \le 10\,000$ .
$1 \le N \le 1\,000\,000$ .

Subtasks

#	Score	Constraints
1	18	$N \le 2\,000$ .
2	29	$N \le 100\,000$ .
3	53	No additional constraints.

Samples

Input

Output

When $N=1$ , the process terminates immediately without making any choice, so the answer is $0.00$ .

Editorial

View editorial