Background

It is said to be the White Polar Shadow; when you see it, only then does the pole stand.

Problem Description

The White Polar Shadow turns into the Pole-Standing Man and comes to the human world, bringing the star function $f(x)$, whose value is the integer closest to $\sqrt[4]x$ $\\$ (that is, $f(x)=\left\lfloor\sqrt[4]x+\dfrac12\right\rfloor$; $\lfloor u\rfloor$ is the value of $u$ rounded down).

Now there are $t$ numbers $n$. For each $n$, the Pole-Standing Man wants to know the value of $\sum\limits_{i=1}^n\dfrac1{f(i)}$. Please tell it.

---

Because the Pole-Standing Man is in a hurry, the $t$ queries in this problem are forced online: each later query must be generated using the answer to the previous query.

You can generate them with the following C++ code (same idea for other languages; you need to include <stdio.h>):

typedef long long ll;
char buf_ans[114];
ll next_n(double last_ans=0,ll get_n=0){
	//last_ans<n<=1e18
	sprintf(buf_ans,"%.6f",last_ans);
	for(ll i=0,x=0;;i++){
		if(buf_ans[i]=='.')return get_n^x;
		if(i&1)x*=10;
		else x=x*10+(buf_ans[i]^48);
	}
}

The first parameter of this function is the answer to the previous query (for the first query, this value is $0$, meaning the first number is not encrypted), and the second parameter is the encrypted number read this time. The function returns the decrypted $n$.

Input Format

The first line contains an integer $t$, indicating the number of datasets (number of queries).

For each dataset, there is only one line containing an integer, representing the encrypted $n$ (the first $n$ is not encrypted).

Output Format

Output one line per query, a number with exactly six digits after the decimal point, representing the answer.

7
1
5
12
95
2040
1145141920209
1070909051

1.000000
4.000000
6.500000
38.666667
403.857143
1475989956.412959
1.000000

Hint

Sample Explanation

After decryption, the queries in sample #1 are:

$$\def\r{\cr\hline} \def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{t}&1&2&3&4&5&6&7\r \textbf{n}&1&4&8&89&2022&1145141919810&1\r \end{array}$$

Constraints

This problem uses bundled tests.

$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & t= & n\le&\bm{\textbf{Score}} \cr\hline 1 & 10&10^6 & 2 \cr\hline 2&1000&10^6&13\cr\hline 3&100&10^9&15\cr\hline 4 &1000&10^{18}&40\cr\hline 5 &%\text{No Special Constraints} 5\times10^5&10^{18}& 30 \cr\hline \end{array}$$

For $100\%$ of the testdata, $10 \le t \le 5\times10^5$, $1 \le n \le 10^{18}$.

Scoring Rules

This problem uses a $\textbf{Special Judge}$. Let the answer you output be $\text{pans}$ and the standard answer be $\text{jans}$. If $\vert \text{pans}-\text{jans}\vert<\text{jans}\times10^{-5}$, then that dataset is accepted. Within one test point, only if all $t$ datasets pass is the whole test point considered passed.

Note that a later $\text{Subtask}$ depends on the previous $\text{Subtask}$. That is, if you did not get points on the previous $\text{Subtask}$, then even if you pass all test points of the later $\text{Subtask}$, you still cannot get the later score.

Translated by ChatGPT 5