#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int coin[17];
int memo[17][301];

int dp(int c, int r){
  if(c == 17 && r == 0) return 1;
  if(c == 17) return 0;
  if(memo[c][r] != -1) return memo[c][r];
  int ret = 0;
  int tmp = r;
  while(tmp >= 0){
    ret += dp(c+1, tmp);
    tmp -= coin[c];
  }
  return memo[c][r] = ret;
}

int main(){
  int n;
  REP(i,17) coin[16-i] = (i+1)*(i+1);
  memset(memo, -1, sizeof(memo));

  while(scanf("%d",&n), n)
    printf("%d\n",dp(0,n));

  return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (= 172), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.

There are four combinations of coins to pay ten credits:

* ten 1-credit coins,
* one 4-credit coin and six 1-credit coins,
* two 4-credit coins and two 1-credit coins, and
* one 9-credit coin and one 1-credit coin.



Your mission is to count the number of ways to pay a given amount using coins of Silverland.



Input

The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.

Output

For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

Example

Input

2
10
30
0


Output

1
4
27

### Response

```cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int coin[17];
int memo[17][301];

int dp(int c, int r){
  if(c == 17 && r == 0) return 1;
  if(c == 17) return 0;
  if(memo[c][r] != -1) return memo[c][r];
  int ret = 0;
  int tmp = r;
  while(tmp >= 0){
    ret += dp(c+1, tmp);
    tmp -= coin[c];
  }
  return memo[c][r] = ret;
}

int main(){
  int n;
  REP(i,17) coin[16-i] = (i+1)*(i+1);
  memset(memo, -1, sizeof(memo));

  while(scanf("%d",&n), n)
    printf("%d\n",dp(0,n));

  return 0;
}
```