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 prime numbers, 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.

Example

Input

2
3
17
41
20
666
12
53
0


Output

1
1
2
3
0
0
1
2
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; ++i)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define PB push_back
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> Point;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1ll << 60;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };

#ifdef WIN32
#include "gtest/gtest.h"
#pragma comment (lib, "gtest.lib")
#define dump(x) cerr << #x << " = " << (x) << "\n"
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n"
#else
#define dump(x)
#define debug(x)
#endif

int n;
#define severalTestCases
static VI primes( 1, 2 );
static bool is_prime[10001];

bool input() {
  cin >> n;
  return n;
}

static short dp[ 1229 ][ 10001 ][ 2 ];

int dfs( int now, int sum, bool check ) {
  if ( !sum ) {
    return 1;
  }
  if ( now == primes.size() || sum < primes[ now ] ) {
    return 0;
  }
  if ( !dp[ now ][ sum ][ check ] ) {
    return dp[ now ][ sum ][ check ];
  }
  int res = 0;
  if ( !check ) {
    res += dfs( now + 1, sum, false );
  }
  res += dfs( now + 1, sum - primes[ now ], true );
  return dp[ now ][ sum ][ check ] = res;
}

int solve(int _n) {
  static bool check = true;
  if ( check ) {
    NCLR( is_prime );
    for ( int i = 3; i * i <= 10000; i += 2 ) {
      if ( is_prime[ i ] ) {
        for ( int j = i * i; j <= 10000; j += i * 2 ) {
          is_prime[ j ] = false;
        }
      }
    }
    for ( int i = 3; i <= 10000; i += 2 ) {
      if ( is_prime[ i ] ) {
        primes.push_back( i );
      }
    }
    NCLR( dp );
    check = false;
  }
  return dfs( 0, n, false );
}

void putsanswer() {
  cout << solve( n ) << "\n";
}

int main( int argc, char **argv ) {
//#ifndef WIN32
#ifdef severalTestCases
  while ( input() ) {
#else
  input();
  putsanswer();
#endif
  /*#else
  ::testing::InitGoogleTest( &argc, argv );
  return RUN_ALL_TESTS();    // gtest 
  #endif*/
#ifdef severalTestCases
  putsanswer();
  }
#endif
  return 0;
}

/*#ifdef WIN32
TEST( testcase, solve ) {
}
#endif*/