题目描述

Silverland的人们使用方形硬币。它们不仅具有方形形状，而且它们的值也是方形数字。Silverland提供硬币，所有方形数字的值最高可达289（= 17 ^ 2）， 即1信用币，4信用币，9信用币，......和289信用币。 有四种硬币组合可以支付十个信用：

十个1信用币， 一个4信用币和六个1信用币， 两个4信用币和两个1信用币， 一个9信用币和一个1 - 信用硬币。

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

输入格式

输入由行组成，每行包含一个整数，表示要支付的金额，后跟一个包含零的行。您可以假设所有金额均为正数且小于300。

当输入为0时，结束输入。

输出格式

对于给定量中的每一个，应输出包含表示硬币组合数量的单个整数的一行。

2
10
30
0

1
4
27