#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"


int main() {
	vector<int>coins;
	for (int i = 1; i < 18; ++i) {
		coins.push_back(i*i);
	}
	vector<vector<int>>dp(600,vector<int>(17));
	dp[0][0] = 1;
	for (int i = 0; i < 300; ++i) {
		for (int j = 0; j < 17; ++j) {
			for (int k = j; k < 17; ++k) {
				dp[i + coins[k]][k] += dp[i][j];
			}
		}
	}
	while (1) {
		int n; cin >> n;
		if (!n)break;
		int sum = 0;
		for (int i = 0; i < 17; ++i) {
			sum += dp[n][i];
		}
		cout << sum << endl;
	}
	return 0;
}
### Prompt

Generate a CPP solution 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 "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"


int main() {
	vector<int>coins;
	for (int i = 1; i < 18; ++i) {
		coins.push_back(i*i);
	}
	vector<vector<int>>dp(600,vector<int>(17));
	dp[0][0] = 1;
	for (int i = 0; i < 300; ++i) {
		for (int j = 0; j < 17; ++j) {
			for (int k = j; k < 17; ++k) {
				dp[i + coins[k]][k] += dp[i][j];
			}
		}
	}
	while (1) {
		int n; cin >> n;
		if (!n)break;
		int sum = 0;
		for (int i = 0; i < 17; ++i) {
			sum += dp[n][i];
		}
		cout << sum << endl;
	}
	return 0;
}
```