Bodensee Coins


People living in the Bodensee area during Roman times used a currency called a thaler. Thalers comes in cubic values from 1 through 9261. For example, some thalers are worth 8 units since 8 is 2 cubed.

Your task is to count the number of ways to pay a given amount using Bodensee thalers. For example, there are 3 ways to pay something that costs 20 thalers: (1) twenty 1 thalers, or (2) one 8 thaler and twelve 1 thalers, or (3) two 8 thalers and four 1 thalers.

Input File -

Input consists of lines each containing an integer amount to be paid. You may assume that all the amounts are positive and less than 10000.

Sample Input File


Output Requirements - bodensee.out

For each of the given amounts to be paid output one line containing a single integer representing the number of ways to pay the given amount using Bodensee thalers.

Sample Output