Problem description

Dodatnią liczbę naturalną nazywamy niezrównoważoną, jeżeli liczby jej dzielników parzystych i nieparzystych bardzo się różnią. Dokładniej, niech E(n) oznacza zbiór dzielników parzystych liczby n, a O(n) oznacza zbiór dzielników nieparzystych. Dodatnia liczba naturalna n jest niezrównoważona wtedy i tylko wtedy, gdy |O(n)| > 2 ⋅ |E(n)| lub |E(n)| > 2 ⋅ |O(n)|.

Napisz program, który wczyta liczbę naturalną N, wyznaczy N-tą najmniejszą liczbę niezrównoważoną i wypisze wynik na standardowe wyjście.

Wejście

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

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – N-ta najmniejsza liczba niezrównoważona.

Ograniczenia

1 ≤ N ≤ 10¹⁸.

Przykład

6

9