Problem description

Problem znajdowania liczb pierwszych jest dość trudny. Inżynierowie z Politechnik nie potrzebują jednak rozwiązywać tak trudnych problemów. Dlatego stworzyli liczby prawiepierwsze.

Liczba jest prawiepierwsza jeśli nie dzieli się przez 2, 3, ani 5. A zatem liczba 10 nie jest prawiepierwsza, zaś 49 jest (choć nie jest pierwsza). Należy zwrócić uwagę, że liczba 5 choć jest pierwsza, nie jest prawiepierwsza.

Napisz program, który: wczyta liczbę N, wyznaczy N-tą liczbę prawiepierwszą i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna N – N-ta liczba prawiepierwsza.

Ograniczenia

1 ≤ N ≤ 10¹⁸.

Częściowa punktacja

W testach wartych łącznie 35% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 1 000 000.

Przykład

2

11