#描述#
People in Silverland use square
coins. Not only they have square shapes but also their values are square
numbers. Coins with values of all square numbers up to 289 (= 17²),
i.e., </span></p>
<p class="MsoNormal" style="text-autospace: none; margin: 6.0pt 0cm">
<span lang="EN-US" style="font-size: 12.0pt">1-credit coins, 4-credit coins,
9-credit coins, . . . , and 289-credit coins, </span></p>
<p class="MsoNormal" style="text-autospace: none">
<span lang="EN-US" style="font-size: 12.0pt">are available in Silverland.</span></p>
<p class="MsoNormal" style="text-autospace: none">
<span lang="EN-US" style="font-size: 12.0pt">There are four combinations of
coins to pay ten credits:</span></p>
<p class="MsoNormal" style="text-autospace: none; margin-top: 6.0pt">
<span lang="EN-US" style="font-size: 12.0pt">ten 1-credit coins</span></p>
<p class="MsoNormal" style="text-autospace: none">
<span lang="EN-US" style="font-size: 12.0pt">one 4-credit coin and six 1-credit
coins</span></p>
<p class="MsoNormal" style="text-autospace: none">
<span lang="EN-US" style="font-size: 12.0pt">two 4-credit coins and two 1-credit
coins</span></p>
<p class="MsoNormal" style="text-autospace: none; margin-bottom: 6.0pt">
<span lang="EN-US" style="font-size: 12.0pt">and one 9-credit coin and one
1-credit coin.</span></p>
<p class="MsoNormal" style="text-autospace: none">
<span lang="EN-US" style="font-size: 12.0pt">Your mission is to count the number
of ways to pay a given amount using coins of Silverland.

#格式#
##输入格式##
The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.

##输出格式##
For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

#样例1#
##样例输入1##

2
10
30
0

##样例输出1##

1
4
27

#限制#
1000ms
32768KB

#提示#

#来源#