Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC). ×

107. 987654321 problem

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

For given number N you must output amount of N-digit numbers, such, that last digits of their square is equal to 987654321.

Input

Input contains integer number N (1<=N<=106)

Output

Write answer to the output.

Sample Input

8

Sample Output

0