Problem Description

Silverland的人们使用方形硬币。它们不仅是方形的，而且它们的面值也是平方数。Silverland有所有平方数硬币的面值，直到289（=17^2），即1个硬币、4个硬币、9个硬币，...，以及289个硬币。

有四种硬币组合可以支付十个硬币：

十个1个硬币，

一个4个硬币和六个1个硬币，

两个4个硬币和两个1个硬币，以及

一个9个硬币和一个1个硬币。

你的任务是计算使用Silverland硬币支付给定金额的方法数量。

Input

输入包括多行，每行包含一个整数，表示要支付的金额，然后是一个包含零的行。您可以假设所有金额都是正数且小于300。

Output

对于给定的每个金额，应输出一行，其中包含一个整数，表示硬币组合的数量。输出中不应出现其他字符。

2
10
30
0

1
4
27