Marinka's Treasure Box#2237

Marinka's Treasure Box

1 second
256 megabytes
Easy

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.

Input

The input file contains a single number (N \leq 12500).

Output

Print a single number — the answer to the problem.

Examples

Example 1

Loading
Loading