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 consists of lines each containing an integer amount to be paid. You may assume that all the amounts are positive and less than 10000.
10 20 77
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.
2 3 22