题目描述

质数又称素数，是大于 $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 \le N \le 100000$ )个数，他想知道每一个整数 $M_i$ ( $2 \le M_i \le 100000$ , $1 \le i \le N$ ) 到底有多少种连续质数相加的方案？请你编程帮助他一下吧。

输入格式

第 $1$ 行一个整数 $N$ ，表示悦悦在纸上写了 $N$ 个整数。

接下来每行一个整数，其中第 $i+1$ 行表示整数 $M_i$ 。

输出格式

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

样例

4
2
12
17
20

1
1
2
0