暂无测试数据。

定义 $p(i)$ 表示第 $i$ 个质数，特别地，当 $i=1$ 时，不引起歧义地我们将 $p(1)$ 省略记为 $p$。

对于任意一个大于 $1$ 的正整数 $n$，我们都能将其以只含有 $p(i)$ 与 $p$ 而不含任何数字的，以乘法运算与复合运算连接的表达式表达。例如：$$\displaystyle \begin{aligned}2&=p\\3&=p(p)\\16&=p*p*p*p\\15&=p(p)*p(p(p))\\131&=p(p*p*p*p*p)\end{aligned}$$

可以证明，对于相同的 $n$，表达式中出现的 $p$ 这个字符的数量总是相同的。将 $p$ 字符的数量记为 $f(n)$。

给定 $m$，你需要求出满足 $f(n)=m$ 的最小的 $n$。

由于 $n$ 可能很大，你只需要求出 $n$ 对一个给定的正整数 $r$ 取模的结果。

输入格式

本题测试点有多组数据。

第一行，一个正整数 $T$，表示数据组数。

接下来 $2T$ 行，对于每组数据：

第一行，一个正整数 $m$。

第二行，一个正整数 $r$。$m,r$ 含义见上。

数据保证 $1\leq m\leq 10^{5000}$，且 $1\leq r\leq 10^9$，$1\leq T\leq 3$。

输出格式

输出 $T$ 行，对于每组数据：

输出一行，一个整数，表示满足 $f(n)=m$ 的最小的 $n$ 对 $r$ 取模的结果。

1
31415926535897932384626433832795
271828183

21643329