题目解析
本题有两种方法可以解决，前者的切入点更平滑，后者更偏向于数学直觉一些。
方法一（并查集）
比较直接的一个想法，从 NNN 开始执行搜索，把 [2,N−1][2, N - 1][2,N−1] 中未加入集合且与当前元素不互质的元素加入集合 SSS。
那么显然我们的目标就是如何快速地找到与 NNN 不互质的元素集合 S′S'S′，对于 S′S'S′ 中的每个元素，再找到与其不互质的元素，以此类推。
由于本题中的操作具有传递性质：XXX 与 YYY 不互质；YYY 与 ZZZ 不互质，那么 XXX，YYY，ZZZ 都属于同一个集合。
我们可以从小到大考虑每个元素 XXX，令 XXX 的最小质因子 P(X)P(X)P(X)，那么有：
1. 若 XXX 为质数，显然集合中只有 XXX 本身。
2. 若 XXX 不为质数，那么显然我们将其拆分为 P(X)P(X)P(X) 与 XP(X)\dfrac{X}{P(X)}P(X)X ，那么二者所在的集合可以借助 XXX 合并起来。
我们将处理到元素 XXX 时，其所在的集合的大小设为 f(X)f(X)f(X)，那么对应的操作次数为 f(X)−1f(X) - 1f(X)−1。
所以我们可以预处理 3×1063 \times 10^63×106 中的所有元素，然后依次回答每个查询即可。
令 M=max(Ni)M = \max(N_i)M=max(Ni )，此方法时间复杂度为 O(Mα(M)+MloglogM+T)\mathrm{O}(M\alpha(M) + M\log{\log{M}} + T)O(Mα(M)+MloglogM+T)。
并查集每个操作平均时间复杂度为 α(M)\alpha(M)α(M)，其中 α\alphaα 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。
方法二（前缀和）
如果仔细分析最终集合 SSS 中的元素会发现，在当 NNN 不为素数时，所有素数 p(⌊N/2⌋<p<N)p(\lfloor N / 2 \rfloor \lt p \lt N)p(⌊N/2⌋<p<N) 都是无法加入到集合中的。其原因从上面的并查集解中不难发现，对于这样元素 ppp 是无法通过拆解 NNN 来使其合并到 NNN 所在的集合的。
我们令 f(N)f(N)f(N) 表示前 NNN 个元素中素数的数量，那么对于每个 NNN，若 NNN 为素数，操作次数为 000，否则为 N−(f(N)−f(⌊N2⌋)−2N - (f(N) - f(\lfloor \frac{N}{2} \rfloor) - 2N−(f(N)−f(⌊2N ⌋)−2。
那么我们在做完筛法后，使用前缀和计算出所有的 f(N)f(N)f(N) 即可。
令 M=max(Ni)M = \max(N_i)M=max(Ni )，此方法时间复杂度为 O(MloglogM+T)\mathrm{O}(M\log{\log{M}} + T)O(MloglogM+T)。
AC代码
方法一（并查集）
方法二（前缀和）
