Vasilică tocmai a învăţat la şcoală despre sistemul de numeraţie cu baza 2. I se pare interesant şi a inventat jocul b210, pe care vrea să îl joace cu prietenul său Gigel. Vasilică îi spune lui Gigel un număr natural nenul n, scris în baza 10. Gigel trebuie să scrie numărul în baza 2, obţinând astfel o secvenţă de cifre binare, care începe cu 1. Asupra scrierii în baza 2 a numărului n Gigel poate aplica una sau mai multe permutări circulare. Printr-o permutare circulară, toate cifrele secvenţei date, exceptând ultima, sunt mutate cu o poziţie spre dreapta, iar ultima cifră devine prima.

De exemplu, dacă n=107, scrierea sa în baza 2 este 1101011. Prin permutări circulare succesive putem obţine, în ordine, secvenţele:

1110101
1111010
0111101
1011110
...

Fiecare astfel de secvenţă este scrierea în baza 2 a unui număr natural, pe care Gigel îl transformă în baza 10. Gigel trebuie să afle care este cel mai mare număr natural m, scris în baza 10, a cărui scriere în baza 2 se poate obţine prin una sau mai multe permutări circulare ale scrierii în baza 2 a numărului n. Lui Gigel jocul nu i se pare aşa interesant şi ar prefera să aibă un program care să determine în locul lui numărul natural m.

Cerința

Scrieţi un program care citeşte numărul natural nenul n şi care determină cel mai mare număr natural m, scris în baza 10, care poate fi obţinut prin una sau mai multe permutări circulare ale scrierii în baza 2 a numărului natural n.

Date de intrare

Fișierul de intrare b210.in conține pe prima linie numărul natural nenul n.

Date de ieșire

Fișierul de ieșire b210.out va conține pe prima linie numărul natural m, cu semnificaţia din enunţ.

Restricții și precizări

• 0 < n ≤ 1.000.000.000

Exemplu

b210.in

13

b210.out

14

Explicație

Scrierea în baza 2 a lui 13 este 1101.

Numărul maxim scris în baza 10 a cărui scriere în baza 2 se poate obţine din permutări circulare ale scrierii în baza 2 a lui 13 este 14, a cărui scriere în baza 2 este 1110.