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ţă
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
• 0 < n ≤ 1000000000
Exemple
b210.in
b210.out
Explicaţii
13
14
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, care are scrierea în baza 2 1110.