Background

Please refer to "Core Cipher A" for the background. Note the only difference between the two problems.

Problem Description

Let $g(n)$ denote the number of different ways $n$ can be expressed as a perfect $k$-th power ($k > 1$). Compute $f(n)=\sum_{i=2}^n \frac{g(i)}{i}$.

For example, $64=2^6=4^3=8^2$, so $g(64)=3$.

Input Format

Multiple queries. The first line contains an integer $T$ indicating the number of queries.

Each of the next $T$ lines contains an integer $n$, asking for $f(n)$.

Output Format

Output $T$ lines. Each line contains a real number representing $f(n)$, with fourteen decimal places.

Due to precision error, your answer will be accepted if the absolute difference from the standard answer is within $2 \times 10^{-14}$.

2
5
15

0.25000000000000
0.48611111111111

Hint

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

For $40\%$ of the testdata, $n \leq 10^6$, $T \leq 5$.

For $100\%$ of the testdata, $2 \leq n \leq 10^{18}$, $1 \leq T \leq 50000$.

Translated by ChatGPT 5