首先直接按题意模拟一下，发现“所有质数都要被选上”这个条件很烦，因为选上一个卡牌后有很多质数会受到影响，非常不好做。换言之，题中的限制很强。

考虑正难则反，钦定一些质数使得它们 恰好 没有被选上，其它质数都被选上。然后会发现 恰好 这个条件还是很强，不好搞，直接上容斥，把 恰好

弱化成 一部分 被选上，另一部分不用管。这样限制条件就松了很多。

回到题目，$n\le 10^6$ 这个条件是唬人的，真正互不相同的数字只有 $2000$ 个，拿桶记一下数 $n$ 就可以扔了。

对于 $s_i\le 30$ 的部分分，显然可以状压预处理然后容斥计算。这为我们提供了一些思路。

[NOI2015] 寿司晚宴 这道题给出了一个相当经典的处理手段：一个数至多有一个 $\gt \sqrt n$ 的质因子，对于 $\le \sqrt n$ 的质因子状压，对于 $\gt \sqrt n$ 的质因子单独考虑。为了方便，称这类质因子为“大质因子”。

本题 $V=2\times 10^3$，发现 $\le \sqrt V$ 的质数只有 $2\sim 43$ 这 14 个，进一步地，$43\times 47\gt 2000$，所以 43 也不用参与状压，进一步压缩了状态。

然后统计，令 $f(i,j)$ 表示前 13 个质数没有被选的状态为 $i$，当前大质因子为 $j$ 时的方案数。预处理是简单的。

然后我们考虑容斥，容易发现容斥系数为 $(-1)^{|S|}$。

计算答案并不难。对于一个状态 $i$，枚举 $j\in [43,2000],j\in \mathbb P$，如果 $j$ 在询问集合中，那么有 $2^{f(i,j)}-1$ 的贡献（筛去空集），反之有 $2^{f(i,j)}$ 的贡献。

把询问集合存成 std::vector，每次就不用枚举 $j$，直接扫一遍 std::vector 然后统计答案，和容斥系数乘起来加到答案里即可。实现可以参考代码。

时间复杂度 $\mathcal O(\sum c_i\times 2^{13})$。