问题描述

质数又称素数，是大于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个整数Mi，要求计算每个Mi有多少种连续质数相加的方案（质数序列连续且无重复使用，和为Mi）。

输入格式

第一行一个整数N，表示悦悦写下的整数个数（1≤N≤300）； 接下来N行，每行一个整数Mi（2≤Mi≤100000），表示需要计算的整数。

输出格式

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

样例输入

4
2
12
17
20

样例输出

1
1
2
0

样例解释

我们先列出足够的质数序列：2、3、5、7、11、13、17、19……

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

数据范围

• 1≤N≤300；
• 2≤Mi≤100000。

、