Square Coins

Interview

Time limit2sMemory limit512 MB

Summary

Count the number of ways to represent each amount below 300 as a sum of square-valued coins (1, 4, 9, ..., 289), with order ignored.

Level: Medium4 of 10
Topics: Dynamic programming, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

People in Silverland use square coins. Not only do the coins have a square shape, but their values are also square numbers. Coins with values of all square numbers up to 289 (= 17^2), that is, 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.

There are four combinations of coins to pay ten credits:

ten 1-credit coins
one 4-credit coin and six 1-credit coins
two 4-credit coins and two 1-credit coins
one 9-credit coin and one 1-credit coin

Your mission is to count the number of ways to pay a given amount using coins of Silverland.

Input

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.

Output

For each of the given amounts, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

Examples1

Example 1
Input
```
2
10
30
0
```
Expected output
```
1
4
27
```