Description

        质数又称素数，是大于1 的正整数，除了1 和它本身外不能被其他自然数整除，有无限个，比如，2、3、5、7 等都是质数，但比如9 就不是质数，因为它除了能被1 和它自己整除外，还能被3 整除。
        悦悦小朋友对这类质数非常感兴趣，因为他发现有一些数是能通过连续的质数相加得到的。比如 5+ 7 + 11 + 13 + 17=53，也就是整数53 可以由连续的质数5、7、11、13、17 相加得到。有时相加的方案还不止一种，比如整数41 就有3 种不同的连续质数相加方案：2+3+5+7+11+13=41，11+13+17=41，还有一种就它本身，即41=41。但也有的数是没有这样加方案的，比如整数20 就找不到连续质数相加的方案，虽然 7 + 13 或者 3 + 5 + 5 + 7 的结果都是20，但前者没有连续，后者质数被重复相加了 。悦悦在纸上写了N（1≤N≤100000）个数，他想知道每一个整数Mi（2≤Mi≤100000，1≤i≤N）到底有多少种连续质数相加的方案？请你编程帮助他一下吧。

Input Format

输入文件prime.in：输入从文件中读取，输入共N+1 行。
第1 行一个整数N，表示悦悦在纸上写了N 个整数。
接下来每行一个整数，其中第i+1 行表示整数Mi。

Output Format

输出文件prime.out：结果输出到文件中，输出共N 行。
输出的第i 行表示整数Mi 有多少种连续质数相加的方案。

4
2
12
17
20

1
1
2
0

Hint

【样例解释】
样例中悦悦写了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≤Mi≤100。
对于50%的数据保证1≤N≤1000，2≤Mi≤1000。
对于100%的数据保证1≤N≤100000，2≤Mi≤100000。

Source

模拟 质因数 前缀和