题目描述

在金银岛上，人们使用的货币的值都为完全平方数，例如1,4,9……289.对于要支付十元的话就有下列四种办法。 1：十个一元的钱。 2：一个四元的，六个一元的。 3：二个四元的，二个一元的。 4：一个九元的，一个一元的。 你的任务在于对于给定的钱数(设其值少于300)，给出有多少种支付的方法.

输入

输入共有n+1行数（n未知），但是输入文件以数字0结束，每行为一个自然数t（1<=t<=300）。

输出

输出共有n行，每行表示输入文件所对应行自然数t，可有多少种完全自然数组成数字t的方案总数。

样例输入

2
10
30
0

样例输出

1 
4
27