Fişierul intrare/ieşire:	bonus.in, bonus.out	Sursă	RMI 2016
Autor	Catalin Francu	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	0.6 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bonus

Parlamentul Federaţiei Galactice, îngrijorat de populaţia aflată în scădere, a decis să arunce un os fiecărui cetăţean din galaxie. Mai precis, Parlamentul a decis să plătească un bonus fiecărui cetăţean a cărui vârstă este un număr rotund (anii au aceeasi durata pe toate planetele datorită Calendarului Standard Galactic). Cârcotaşii au obiectat că speciile folosesc baze diferite în sistemul lor de numeraţie, aşadar numerele rotunde nu pot fi definite. După multe deliberări, Parlamentul a decis că o vârstă A va fi considerată rotundă dacă se poate scrie ca (două cifre de 1 şi zero sau mai multe cifre de 0) într-o bază B, oricare ar fi aceasta. Cantitatea bonusului este cea mai mică bază B, în care numărul A este rotund.

Odată ce legea a intrat în vigoare, Parlamentul a avut nevoie de o metodă rapidă de a determina bonusurile, astfel încât cetăţenii să poată primii banii înainte de viitoarele alegeri.

Date de intrare

Fişierul de intrare bonus.in conţine pe prima linie numărul N, reprezentând numărul de cetăţeni din galaxie. Pe următoarele N linii se află numerele întregi A₁, A₂, A₃, ... A_n, reprezentând vârstele cetăţenilor.

Date de ieşire

În fişierul de ieşire bonus.out conţine N linii. Linia i trebuie să conţină un singur număr, cea mai mică bază în care A_i este un număr rotund.

Restricţii

• 1 ≤ N ≤ 100.000
• pentru 20% din teste 1 ≤ N ≤ 10.000
• 2 ≤ A_i ≤ 2⁶⁴-1 pentru orice 1 ≤ i ≤ N

Exemplu

Explicaţie

Unele numere sunt rotunde în baze multiple. Spre exemplu 36 este rotund şi în baza 3: 36 = 1100₃. Totuşi, răspunsul trebuie să fie mereu cea mai mică bază.

Cum se trimit solutii?