spoj#TPC07. Change

Change

How many ways are there to pay n cents? We assume that the payment must be made with pennies (1 cent), nickels (5 cents), dimes (10 cents), quarters (25 cents), and half-dollars (50 cents).

For example, there are four ways to pay 13 cents, namely (13 pennies), (2 nickels, 3 pennies), (1 nickel, 8 pennies), and (1 dime, 3 pennies).

Input

The input will contain multiple test cases. Each test case contains a single line with a single integer n (1 ≤ n ≤ 1000000000).

The input will be terminated by the end of file.

 

Output

For each input integer n, output how many ways are there to pay n cents in a single line.

Sample Input

13
100000000

 

Sample Output

4
66666793333412666685000001