作为 $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$ 取模)
$10$ 个筛码为前 $10$ 个质数,因此只有不含有这些质因子的数能被计数。
按题目方法数数,可以得到序列 $1,31,37,41,43,...$,因此答案为 $43$。