2006. 助手酱想要知道密码!

时间限制 3000 ms   内存限制 256 MB

作为 $Labman-004$,Christina 当然有权使用电话微波炉(暂定)来发送 D-Mail。

但是电话微波炉(暂定)是 lab 的重要战略资源,为了让非 lab 成员不能随意使用,凤凰院凶真改造了它,给它加上了密码锁。

密码锁的密码是动态的。每个 Labman 都有一个手表,上面会有数个动态码指示当天电话微波炉(暂定)的密码为多少,获得密码的规则如下:

动态码共有 $11$ 个,前 $10$ 个数为筛码 $P_i$$(0 \leq i \leq 9)$,最后一个数为位码 $N$,密码为从 $1$ 开始第 $N$ 个不能被任何一个 $P_i$ 整除的数。

Christina 虽然是提出了时间旅行可能性的天才,但她并不是很擅长数学,而且 $N$ 实在太大了!于是她找到了你,希望你能帮她算出密码。Christina 每天都会来找你,直到她不需要再使用电话微波炉(暂定)为止,因此你需要回答她的 $Q$ 次询问。

这个密码可能会很大,为了让 Labman 们不至于花太多时间在输密码上,真正的密码为上述计算结果对 $998244353$ 取模。

输入数据

第一行为一个整数 $Q$,为Christina的询问次数。$1 \leq Q \leq 100$

接下来 $Q$ 行每行有 $11$ 个数字,前 $10$ 个数字为筛码,最后 $1$ 个为位码。

题目保证 $2 \leq P_i \leq 10^{18}$,$\prod_{i=0}^9 P_i \leq 10^{18}$,$1 \leq N \leq 10^{180}$,且答案一定存在。

注意 $\prod$ 表示连乘,即 $P_0, P_1,..., P_9$ 的乘积。

输出数据

输出共 $Q$ 行,每行输出一个整数,表示求得的密码。(注意对 $998244353$ 取模)

样例输入

复制
1
2 3 5 7 11 13 17 19 23 29 5 \n
 · · · ·  ·  ·  ·  ·  ·  · \n

样例输出

复制
43  \n

样例说明

$10$ 个筛码为前 $10$ 个质数,因此只有不含有这些质因子的数能被计数。

按题目方法数数,可以得到序列 $1,31,37,41,43,...$,因此答案为 $43$。

提交

请先 登录

© 2024 FAQs Contact About