12月将举办首届西电ACM新生赛,敬请期待~~~~

问题 1210. -- 尧老师要教孩子做算术

1210: 尧老师要教孩子做算术

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交][状态][讨论版]

题目描述

尧老师要教孩子做算术 - 副本.md

尧老师的孩子想让尧老师陪他去游乐园玩,但是此时尧老师正在证明秦莞尔猜想。为了让孩子不再打扰他,他扔给了的孩子一个算术题,表示如果能在1S内解出就同意一起出去玩。虽然他是尧老师的孩子,但他毕竟只有三岁(如果有一分钟的话也许能解出来)。于是他求助你:

​ 定义 为素数且互不相同), 的值为使 成立的 的个数 次询问,每次询问给定一个 ,问 的值。

输入

尧老师要教孩子做算术.md

不超过50组数据。

每组数据第一行包含一个整数 ,第二行包含个整数

第三行包含一个整数 ,接下来 行每行包含一个整数

输出

尧老师要教孩子做算术 - 副本.md

对于每个询问输出一个整数,输出 的值。

注意答案可能过大,请将答案对第 个素数取膜后输出。

样例输入

2
2 3
1
2

样例输出

4

提示





尧老师要教孩子做算术 - 副本.md


样例询问的是有多少不同的 ,满足 ,显然只有 四种。



来源

[提交][状态][讨论版]