题目描述

质数又称素数，是大于 $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$ 本身；
• $20$ 没有符合条件的方案（$7+13$ 不连续，$3+5+5+7$ 重复使用质数）。

现在给定 $N$ 个整数 $M_i$，要求计算每个 $M_i$ 有多少种连续质数相加的方案（质数序列连续且无重复使用，和为 $M_i$）。

输入格式

第一行一个整数 $N$，表示悦悦写下的整数个数。
接下来 $N$ 行，每行一个整数 $M_i$，表示需要计算的整数。

输出格式

输出 $N$ 行，第 $i$ 行表示整数 $M_i$ 对应的连续质数相加方案数。

样例

4
2
12
17
20

1
1
2
0

样例解释
列出足够的质数序列：$2, 3, 5, 7, 11, 13, 17, 19 \dots$

1. $M_i=2$：只有质数 $2$ 本身这 $1$ 种方案，答案为 $1$；
2. $M_i=12$：唯一符合条件的是 $5+7=12$（连续质数），答案为 $1$；
3. $M_i=17$：有两种方案，分别是 $17$ 本身，以及 $2+3+5+7=17$（连续质数），答案为 $2$；
4. $M_i=20$：不存在连续质数相加和为 $20$ 的情况，答案为 $0$。

数据范围

• $1 \le N \le 300$
• $2 \le M_i \le 100000$