P8319 "JROI-4" Fractions.

In QQ groups, you often see this kind of chain: - Ten-thousand-person petition xxx $(1/10000)$ $\to$ - Ten-thousand-person petition xxx $(1/5000)$ $\to$ - Ten-thousand-person petition xxx $(1/2500)$ $\to$ - Ten-thousand-person petition xxx $(1/1250)$ $\to \dots$ And so on. When the fraction can be reduced, the “ten-thousand-person petition” can be completed very quickly.

The process of an “$x$-person petition” can be seen as a function $f(x)$: There is a fraction $\frac{0}{x}$. Repeat the following steps until this fraction becomes $1$: 1. Add $1$ to the numerator. 2. If this fraction can be reduced, reduce it to its simplest form. Now Xiao D gives you $T$ test cases. In each test case, you are given $n$. You need to find, for $1 \le x \le n$, the maximum number of operations of $f(x)$. But he is too weak and cannot do it. Can you help him?

The first line contains a positive integer $T$. The next $T$ lines each contain a positive integer $n$.

Output $T$ lines. Each line contains an integer $s$, meaning the maximum number of operations of $f(x)$ for $1 \le x \le n$.

### Sample Explanation $f(1)=1,f(2)=2,f(3)=3,f(4)=3,f(5)=5$. I also want to list larger values of $f(x)$, but there is not enough space. ### Constraints For all testdata, $1 \le T \le 5 \times 10^5$, $1 \le n \le 2 \times 10^6$. Parts not filled in the Subtasks table mean they are the same as the constraints for all data. | Subtask ID | Range of $T$ | Range of $n$ | Special Property | Score | | -----------: | -----------: | -----------: | -----------: | -----------: | | Subtask $1$ | $T \le 3$ | $n \le 10$ | | $10$ | | Subtask $2$ | $T \le 5$ | $n \le 10^3$ | | $30$ | | Subtask $3$ | | | $n$ is prime. | $10$ | | Subtask $4$ | | $n \le 5 \times 10^5$ | | $20$ | | Subtask $5$ | | | | $30$ | Translated by ChatGPT 5