质数又称为素数，是大于 1 的正整数，除了 1 和它本身外不能被其他自然数整除，有无限个。比如，2、3、5、7 等都是质数，但 9 就不是质数，因为它能被 3 整除。

数学老师最近对某些整数非常感兴趣，因为他发现有这些数能通过连续的质数相加得到。比如 53 可以由 5、7、11、13、17 相加得到，5+7+11+13+17=53。有时相加的方案还不止一种，比如 41 就有 3 种不同的连续质数相加方案：2+3+5+7+11+13=41，11+13+17=41，41=41。

但是也有的数没有这样的相加方案，比如 20 就找不到连续质数和相加的方案，虽然 3+17=20 或 3+5+5+7=20，但前者没有连续，后者质数重复相加了。

数学老师在纸上下了 N 个数，他想知道每个整数 M_i 到底有多少种连续质数相加的方案，请你编程帮他一下吧。

第一行一个整数 N ，表示有 N 个整数。

第二行到第 N+1 行，第 i+1 行一个整数 M_i。

输出共 N 行，第 i 行表示整数 M_i 有多少种连续质数相加的方案。

【样例 1 解释】

样例中有 4 个整数，分别是 2,12,17 和 20。

因为2=2，所以 2 有 1 种方案。

因为5+7=12，所以 12 有 1 种方案。

因为2+3+5+7=17，17=17，所以 17 有 2 种方案。

20 没有满足条件的额方案，所以输出 0。

【数据范围】

对于 30\% 的数据：1≤N≤100，2≤M_i≤100。

对于 50\% 的数据，1≤N≤1000，2≤M_i≤1000。

对于 100\% 的数据，1≤N≤10^5，2≤M_i≤10^5。

婺城区第二届青少年信息素养大赛初中组试题

市赛素数筛