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 (=17^2), 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.

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.

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.

2
10
30
0

1
4
27

/*题解：
	母函数模板，理解模板的每一步是关键 
	*/ 
#include<cstdio>
#include<cstring>
int main()
{
    int n,i,j,k,c1[1010],c2[1010];
    while(scanf("%d",&n)&&n)
	{
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(i=0; i<=n; i++)       //初始化 
            c1[i]=1;
        for(i=2; i*i<=n; i++)     //i到n遍历，i指第i个表达式，一个括号是一个表达式 
		{
            for(j=0; j<=n; j++)   //一个表达式第j个变量(1+x^2+x^4....)里，第j个就是x^(2*j). 
			{
                for(k=0; k+j<=n; k+=i*i) //k每次增加i. 
				{
                    c2[k+j]+=c1[j];
                }
            }
            for(j=0; j<=n; j++)
			{
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}