A37634.数的集合

给定一个集合 $S$，一开始时，集合中只有一个数 $N$。接下来你可以执行以下操作：

• 从 $2$ 到 $N$ 中选择一个集合中没有的数 $X$ 加入集合 $S$ 中。对于 $X$，要求存在 $Y \in S$ 使得 $\gcd{(X, Y)} \gt 1$。$\gcd{(X, Y)}$ 表示 $X$ 和 $Y$ 的最大公约数。

请你计算最多可以执行多少次以上操作。

每个测试文件包含 $\tt{T}$ 个测试用例。

$\large{数据范围}$

• $1 \le T \le 10^5$
• $2 \le N \le 3 \times 10^6$

对于每个测试文件，格式如下：

$\tt{T}$
$\tt{Testcase_1}$
$\tt{Testcase_2}$
$\tt{\vdots}$
$\tt{Testcase_T}$

对于每个 $\tt{Testcase}$ 格式如下：

$\tt{N}$

对于每个 $\tt{Testcase}$ 在单独的一行中输出答案。

$\bf{样例\ 1：}$

无法执行操作。

$\bf{样例\ 2：}$

1. 选择 $X = 6$ 加入到 $S$ 中，$\gcd{(6, 8)} = 2$，此时 $S = \{6, 8\}$。
2. 选择 $X = 4$ 加入到 $S$ 中，$\gcd{(4, 8)} = 4$，此时 $S = \{4, 6, 8\}$。
3. 选择 $X = 2$ 加入到 $S$ 中，$\gcd{(2, 4)} = 2$，此时 $S = \{2, 4, 6, 8\}$。
4. 选择 $X = 3$ 加入到 $S$ 中，$\gcd{(3, 6)} = 3$，此时 $S = \{2, 3, 4, 6, 8\}$。

总共可以执行 $4$ 次操作。