P3766 Core Cipher B

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

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$.

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 $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}$.

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