#include <cstdio>

#include <cstring>

using namespace std;

int method[10001][1300];

int dp[10001];

bool isntprime[10001];

int heap[1300],cnt;

void calprime(){

    method[2][0]=1;

    dp[2]++;

    heap[cnt++]=2;

    for(int i=3;i<10001;i+=2){

        if(!isntprime[i]){

            heap[cnt]=i;

            method[i][cnt++]=1;dp[i]++;

            for(int j=3;i*j<10001;j+=2){

                isntprime[i*j]=true;

            }

        }

    }

}

void caldp(){

    for(int i=2;i<10001;i++){

        for(int j=0;j<cnt;j++){

            if(method[i][j]!=0){

                if(j<cnt-1&&i+heap[j+1]<10001){

                    method[i+heap[j+1]][j+1]+=method[i][j];

                    dp[i+heap[j+1]]+=method[i][j];

                }

            }

        }

    }

}

int main(){

    calprime();

    caldp();

    int n;

    while(scanf("%d",&n)==1&&n){

        printf("%d\n",dp[n]);

    }

    return 0;

}