卡了半天竟然卡在输入上面了，，，我恨。非文件末尾不要用while（scanf）。

下面是题目复述：

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive primenumbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.

Your mission is to write a program that reports the number of representations for the given positive integer.

Input

The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.

Output

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.

Sample

Input

2

3

17

41

20

666

12

53

0

Output

1

1

2

3

0

0

1

2

下面是解题思路：

题目大意是输入几个数字以0结尾，每个数字是否能通过连续的质数相加得到，输出有几种连续相加方式。

暴力解题。先把10000以内的素数打表，然后从2开始尝试后面的数字相加是否等于n即可。满足条件则种类+1。

下面是AC代码：

#include <iostream>
#include <cstdio>
const int N=1e4+10;

using namespace std;
bool str[N];
int prime[N];
int num=0;
void in()
{
    for(int i=2; i<=N; i++)
    {
        if(!str[i])
        {
            prime[num++]=i;
            for (int j=i+i; j<=N; j+=i) str[j]=true;
        }
    }
    //for(int i=0;i<num;i++) cout << prime[i]<<endl;

}
int n;
int main()
{
    in();
    while (1)
    {
        scanf("%d",&n);
        if(n==0) break;

        int ans=0;

        for(int i=0; i<=num; i++)
        {
            int sum=0;
            for(int j=i; j<=num; j++)
            {
                sum+=prime[j];
                if(sum==n)
                {
                    ans++;
                    break;
                }
                if(sum>n) break;
            }
        }

        printf("%d\n",ans);

    }
    return 0;
}