Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given all $N - 1$ integers in the range $[2, N]$. In each step, you choose $2$ distinct integers and if they share a common factor greater than $1$, you combine them into the same group. You keep doing it until no further merging is possible.

Belonging to a group is an equivalence relation. So if integers $a$ and $b$ are in the same group and integers $b$ and $c$ are in the same group, then integers $a$ and $c$ are also said to be in the same group.

Find the total number of groups formed in the end.

------ Input ------

First line will contain $T$, number of test cases. Then the test cases follow.
Each test case contains a single line of input, a single integer $N$.

------ Output ------
For each test case, output in a single line the answer to the problem.

------ Constraints ------
$1 ≤ T ≤ 2\cdot 10^{5}$
$2 ≤ N ≤ 10^{7}$

------ Subtasks ------
Subtask #1 (30 points):
$1 ≤ T ≤ 200$
$2 ≤ N ≤ 1000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------
3

2

4

8
----- Sample Output 1 ------
1

2

3
----- explanation 1 ------
Test Case $1$: The final group is $\{2\}$.

Test Case $2$: The final groups are $\{2, 4\}$, and $\{3\}$.

Test Case $3$: The final groups are $\{2, 3, 4, 6, 8\}$, $\{5\}$, and $\{7\}$.

见题面

见题面