Description

在金银岛上，人们使用的货币的值都为完全平方数，例如1、4......289

对于要支付十元的话就有下列四种办法：

1:十个一元的钱。

2:一个四元的。六个一元的。

3:二个四元的,二个一元的。

4: 一个九元的，一个一元的。

你的任务在于对于给定的钱数(设其值少于300)，给出有多少种支付的方法.

Format

Input

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

Output

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

Samples

2
10
30
0

1
4
27