#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

ll dp[305];

int main()
{
//	cut here before submit 
//	freopen ("testcase.SC", "r", stdin );
	memset (dp, 0LL, sizeof (dp ) );
//	rep (j, 300 + 1 ){
	dp[0] = 1LL;

	for (int i = 1; i <= 17; i++ ){
		for (int j = 1; j <= 300; j++ ){
			if (j - i*i < 0 ) continue;
			dp[j] += dp[j - i*i];
		} // end for
	} // end for

	int n;
	while (scanf ("%d", &n ), n ){
		printf ("%ld\n", dp[n] );
	} // end loop
		
	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 <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

ll dp[305];

int main()
{
//	cut here before submit 
//	freopen ("testcase.SC", "r", stdin );
	memset (dp, 0LL, sizeof (dp ) );
//	rep (j, 300 + 1 ){
	dp[0] = 1LL;

	for (int i = 1; i <= 17; i++ ){
		for (int j = 1; j <= 300; j++ ){
			if (j - i*i < 0 ) continue;
			dp[j] += dp[j - i*i];
		} // end for
	} // end for

	int n;
	while (scanf ("%d", &n ), n ){
		printf ("%ld\n", dp[n] );
	} // end loop
		
	return 0;
}
```