Rashad is trying to sleep#10200

Rashad is trying to sleep

1 second
64 megabytes
Hard

Rashad has problems with sleeping. Sleeping is most important for scientists and programmers, because their brains work a lot. Huseyn told Rashad a very interesting technique that will help him to sleep: at night Rashad must find the -th interesting number. An interesting number is a number where the last digits of its square are identical to the number itself. For example, is an interesting number, because 376 \cdot 376 = 141376. The last digits of are , and they are identical to the number. While Rashad was trying to find the -th interesting number, he went to his sweet dream. Can you find the -th interesting number?

Input

One integer (1 \leq k \leq 1000).

Output

Print the -th interesting number.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading