http://acm.hdu.edu.cn/showproblem.php?pid=1398
//1304230 2009-04-24 14:13:00 Accepted 1398 0MS 260K 523 B C++ no way 
#include<iostream>
using namespace std;
int main()
{
    int squares[17]={1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289};
    //所有硬幣的種類及面值
    int i,j,k;
    int num[301],temp[301];
    for(i=0;i<=300;i++)
    {
        num[i] = 1;
        temp[i] = 0;
    }
    for(i=2; i<=17; i++)
    {    
        for(j=0;j<=300;j++)
        {
            for(k=0 ; k+j<=300; k+=squares[i-1]) 
            {    
                temp[j+k] += num[j];    
            }
        }
        for (j=0;j<=300;j++)
        {    
            num[j] = temp[j];    
            temp[j]=0;    
        }
    }
    while(cin>>k && k)
    {
        cout<<num[k]<<endl;
    }
    return 0;
}