Description

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

Input Format

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

Output Format

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

2
10
30
0

1
4
27

Source

动态规划 背包问题