扎实的数学功底是每个信息学竞赛选手必须具备的基本素养之一。

比如计算一个正整数$m$有多少个正约数，通常的做法是先将$m$分解质因数，将每个质因数的幂次加一之后乘起来。例如$60=2^2\times3\times5$，质因数的幂次分别为$2,1,1$，因此$60$有$(2+1)(1+1)(1+1)=12$个正约数。

现在nodgd给你一个正整数序列$a_1,a_2,\dots,a_n$，并进行很多次询问：序列前$k$个数的乘积有多少个正约数的所有质因数都不超过$p$呢？特别的，$1$没有质因数，所以无论怎么询问$1$总是符合条件。

第一行两个整数$n,q$，表示序列的长度和询问的次数。

第二行$n$个正整数$a_1,a_2,\dots,a_n$。

从第三行起的连续$q$行，每行两个正整数$k,p$，表示一次询问。

对于每次询问，输出答案$\mod{998244353}$后的值。

样例说明

• 第$2,3$次询问分别是问$12$有多少个正约数的质因数不超过$3$和$2$。$12$的所有正约数（$1,2,3,4,6,12$）的质因数都不超过$3$，共有$6$个；其中$1,2,4$的质因数不超过$2$，共有$3$个。
• 第$4,5$次询问分别是问$360$有多少个正约数的质因数不超过$4$和$5$。$360$的所有正约数的质因数都不超过$5$，共有$24$个，其中$1,2,3,4,6,8,9,12,18,24,36,72$这$12$个正约数的质因数不超过$4$。

数据规模与约定

对于5%的数据，\(n=1,\quad q,a_i,p\leq1000\)；

对于15%的数据，\(n,q,a_i,p\leq 1000\)；

对于另外15%的数据，\(a_i,p\leq 20\)；

对于另外15%的数据，所有$a_i$都是$2$的整数次幂；

对于另外15%的数据，每次询问的$p$不小于序列中任何一个$a_i$；

对于100%的数据，$1\leq n,q,a_i,p\leq10^5,\quad 1\leq k\leq n$。