问题描述

具体描述见教材p253： 在金银岛上，人们使用的货币的值都是完全平方数，例如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

限制

1s, 64MB.