Marinka is Igor's younger sister, and she is not very good at counting yet. Therefore, she often asks Igor to count things for her. To reduce these requests, Igor started teaching Marinka arithmetic. Everything was going well until Marinka learned that , , and are prime numbers. Marinka has a piggy bank where she collects coins of , , and rubles (with rubles being a very rare coin!).
Now Marinka is interested only in positive integers that have no prime divisors other than , , and . She has started asking Igor to name such numbers. At first, Igor thought he could easily answer her questions, but he realized that for large it is not so simple.
Help Igor by writing a program that calculates the -th positive integer that has no prime divisors other than , , and .
By the way, if someone does not know, a prime number is an integer that is only divisible by and itself.
The input file contains a single number (N \leq 12500).
Print a single number — the answer to the problem.
Example 1