According to unconfirmed rumors the banking reform is approaching, and you decide to make for it some proposals - and what if they suddenly will be accepted, and even you will be payed for these ideas?

Your idea is to change the denominations in coin circulation. By your opinion, it should be coins 1, 5, 10, 25 and 50 and how to call the petty cash - let the central bank decides.

However, the Central Bank has immediately demanded you to provide information about how many ways are there to represent in cash the given amount of money up to 7489 inclusive. Why up to this amount? And how the bank will name them? But who knows: the bankers have their quirks, we also name them for simplicity, just coins.

For example, an amount of 11 units can be represented in the form 10 * 1 coin + 1 * 1 coin, or 5 * 2 coins + 1 * 1 coin, or 5 * 1 coin + 1 * 6 coins or 11 * 1 coin, i.e. total in four ways.

Your task is to write a program to count the number of ways - to quickly respond to any request from the bankers.

Input

Each line contains one positive integer - the next bank request.

Output

For each request print on a separate line the required number of ways to provide a specified amount.