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

定义 （ 为素数且互不相同）， 的值为使 成立的 的个数 。 次询问，每次询问给定一个 ，问 的值。

不超过50组数据。

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

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

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

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

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