#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void MakeData(int, int, bool, vector<int>, vector<int>&);
void NextData(vector<int>, vector<int>&);

int main(){
  int i, n;
  vector<int> coin, data;

  for(i=1; i<=17; ++i) coin.push_back(i*i);

  while(1){
    cin >> n;
    if(n == 0) break;
    MakeData(n, n, true, coin, data);

    for(i=1; data[0]!=1; ++i) NextData(coin, data);
    cout << i << endl;
    data.clear();
  }
  return 0;
}

void MakeData(int n, int m, bool is_upper,
	      vector<int> coin, vector<int>& data){
  vector<int>::iterator i;
  if(is_upper) i = upper_bound(coin.begin(), coin.end(), m);
  else i = lower_bound(coin.begin(), coin.end(), m);
  --i;
  while(1){
    if(n >= *i){
      data.push_back(*i);
      n -= *i;
      if(n == 0) return;
    }else{
      --i;
    }
  }
}

void NextData(vector<int> coin, vector<int>& data){
  int n, sum;
  vector<int>::iterator i, j;
  i = find(data.begin(), data.end(), 1);
  n = *(i-1);
  if(i == data.end()){
    data.pop_back();
    MakeData(n, n, false, coin, data);
  }else{
    for(j=i-1, sum=0; j!=data.end(); ++j) sum += *j;
    data.erase(i-1, data.end());
    MakeData(sum, n, false, coin, data);
  }
}
### Prompt

Please create a solution in CPP to the following problem:

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<vector>
#include<algorithm>

using namespace std;

void MakeData(int, int, bool, vector<int>, vector<int>&);
void NextData(vector<int>, vector<int>&);

int main(){
  int i, n;
  vector<int> coin, data;

  for(i=1; i<=17; ++i) coin.push_back(i*i);

  while(1){
    cin >> n;
    if(n == 0) break;
    MakeData(n, n, true, coin, data);

    for(i=1; data[0]!=1; ++i) NextData(coin, data);
    cout << i << endl;
    data.clear();
  }
  return 0;
}

void MakeData(int n, int m, bool is_upper,
	      vector<int> coin, vector<int>& data){
  vector<int>::iterator i;
  if(is_upper) i = upper_bound(coin.begin(), coin.end(), m);
  else i = lower_bound(coin.begin(), coin.end(), m);
  --i;
  while(1){
    if(n >= *i){
      data.push_back(*i);
      n -= *i;
      if(n == 0) return;
    }else{
      --i;
    }
  }
}

void NextData(vector<int> coin, vector<int>& data){
  int n, sum;
  vector<int>::iterator i, j;
  i = find(data.begin(), data.end(), 1);
  n = *(i-1);
  if(i == data.end()){
    data.pop_back();
    MakeData(n, n, false, coin, data);
  }else{
    for(j=i-1, sum=0; j!=data.end(); ++j) sum += *j;
    data.erase(i-1, data.end());
    MakeData(sum, n, false, coin, data);
  }
}
```