Problem description

Jasio, jak każdy informatyk uwielbia cyfry 0 i 1. Lubi także liczby podzielne przez N. Chciałby połączyć te dwa zainteresowania i wymyślił zadanie.

Napisz program, który: wczyta liczbę N, wyznaczy najmniejszą liczbę złożoną tylko z cyfr 0 i 1, która jest podzielna przez N i wypisze wynik na standardowe wyjście.

Wejście

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

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – najmniejsza możliwa złożona tylko z cyfr 0 i 1, podzielna przez N.

Ograniczenia

1 ≤ N ≤ 1 000 000.

Przykład

5

10

7

1001