Description

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?

Input Format

The first line contains a positive integer $T$.

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

Output Format

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

5
1
2
5
8
114514

1
2
5
7
114493

Hint

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.

Translated by ChatGPT 5