题目描述

在金银岛上，人们使用的货币的值都是完全平方数，例如 1 ， 4 ， 9 ， ... ，289 。支付 10 元钱有下列 4 种方法：

(1) 10 个 1 元的钱;

(2) 1 个 4 元的， 6 个 1 元的；

(3) 2 个 4 元的， 2 个 1 元的；

(4) 1 个 9 元的， 1 个 1 元的。

你的任务是对于给定的钱数(设其值少于300)，求出支付方法的总数。

输入格式

共有 n+1 行（ n 未知），以数字 0 结束，每行为一个自然数 t ( 1 ≤ t ≤ 300 )。

输出格式

共有 n 行，每行表示对于给定的钱数 t ，对应的支付方案总数。

样例

2
10
30
0

1
4
27