#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount
#define clear(arr, val) memset(arr, val, sizeof(arr))

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



int main()
{
	vector<int> coins;
	for (int i = 1; i * i <= 300; ++i)
		coins.push_back(i * i);

	int dp[33][333];
	clear(dp, 0);
	dp[0][0] = 1;
	//for (int i = 0; i < coins.size(); ++i)
	//	for (int j = 0; j <= 300; ++j)
	//		for (int k = 0; k * coins[i] <= j; ++k)
	//			dp[i + 1][j] += dp[i][j - k * coins[i]];
	for (int i = 0; i < coins.size(); ++i)
		for (int j = 0; j <= 300; ++j)
			dp[i + 1][j] = dp[i][j] + (j >= coins[i] ? dp[i + 1][j - coins[i]] : 0);

	int n;
	while (scanf("%d", &n), n)
		printf("%d\n", dp[coins.size()][n]);
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount
#define clear(arr, val) memset(arr, val, sizeof(arr))

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



int main()
{
	vector<int> coins;
	for (int i = 1; i * i <= 300; ++i)
		coins.push_back(i * i);

	int dp[33][333];
	clear(dp, 0);
	dp[0][0] = 1;
	//for (int i = 0; i < coins.size(); ++i)
	//	for (int j = 0; j <= 300; ++j)
	//		for (int k = 0; k * coins[i] <= j; ++k)
	//			dp[i + 1][j] += dp[i][j - k * coins[i]];
	for (int i = 0; i < coins.size(); ++i)
		for (int j = 0; j <= 300; ++j)
			dp[i + 1][j] = dp[i][j] + (j >= coins[i] ? dp[i + 1][j - coins[i]] : 0);

	int n;
	while (scanf("%d", &n), n)
		printf("%d\n", dp[coins.size()][n]);
}
```