Problem description
Liczby mikrocząsteczkowe
(mikroczasteczki)
Liczbę naturalną dodatnią nazwiemy mikrocząsteczkową, jeśli wszystkie liczby w jej rozkładzie na czynniki pierwsze są nie większe niż 5. Oczywiście najmniejszą liczbą mikrocząsteczkową jest 1, drugą z kolei jest 2, a siódmą z kolei jest 8, itd.
Twoim zadaniem jest wypisanie na wyjściu N-tej, w porządku rosnącym, liczby mikrocząsteczkowej.
Wejście
W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N – numer poszukiwaniej liczby mikrocząsteczkowej.
Wyjście
Na wyjście należy wypisać jedną liczbę naturalną – N-tą liczbę mikrocząsteczkową.
Ograniczenia
1 ≤ N ≤ 109.
Podzadania
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | N ≤ 10 000 | 20 |
| 2 | N ≤ 1 000 000 | 20 |
| 3 | brak dodatkowych ograniczeń | 60 |
Przykład
| Input | Output | |
|
|
| Input | Output | |
|
|