题目描述
s国的人们用的硬币很有特点,每种硬币的面值都是n(1<=n<=17)的平方,即面值分别为1,4,9,16......289
例如有4种组合的硬币可以支付10元
10个1元硬币,
1个4元硬币和6个1元硬币,
2个4元硬币和2个1元硬币,和
1个9元硬币和1个1元硬币。
你的任务是计算支付指定金额的硬币组合数。
输入描述
每行输入一个数,表示想要计算的金额(所有金额不超过300),输入0时结束
输出描述
每个输入对应一个输出,代表金额对应的组合数。
样例输入
2
10
30
0
样例输出
1
4
提示