你有一个长度为 $N$ 的序列 $A_1, A_2, \cdots, A_N$，其中 $A_i=i$. 你还有一个长度为 $N$ 的序列 $B_1, B_2, \cdots, B_N$，其中 $B_i=\text{第 }i\text{ 小的素数}$. 每次操作，你可以任选一段区间 $[L,R]$ 和一个正整数 $K$，满足 $1 \le L \le R \le N$ 且 $K \ge 1$，并对序列 $\{A\}$ 中位于区间 $[L,R]$ 内的**每一个元素**都加上 $K$. 问最少操作多少次，才能够使序列 $\{A\}$ 变为序列 $\{B\}$？

第一个包含一个正整数 $T$ $(1 \le T \le 10^4)$，表示数据组数。 每组数据占一行，包含一个整数 $N$ $(1 \le N \le 10^7)$.

对于每组数据，在一行内输出一个整数，表示答案。

在 $N = 1$ 时： - $\{A_1\} = \{1\}$ - $\{B_1\} = \{2\}$ 取 $[L,R]=[1,1],\ K = 1$，操作一次即可。 在 $N = 2$ 时： - $\{A_1,A_2\} = \{1,2\}$ - $\{B_1,B_2\} = \{2,3\}$ 取 $[L,R]=[1,2],\ K = 1$，操作一次即可。

2023-05 多校联合训练 ZJNU站 正式赛