Fişierul intrare/ieşire:	bonus.in, bonus.out	Sursă	RMI 2016
Autor	Cristian Francu	Adăugată de	Cristian Francu •francu
Timp execuţie pe test	1 sec	Limită de memorie	512 kbytes
Scorul tău	N/A	Dificultate	5/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise

Bonus galactic (clasele 11-12)

Parlamentul Federaţiei Galactice, în scădere de popularitate, a hotarît să mai arunce un os fiinţelor inteligente din galaxie. Mai exact, a hotărît să dea o primă tuturor galaxienilor care împlinesc o sumă rotundă de ani. Propunerea de lege a fost atacată însă de diverşi oportunişti, pe motivul că sistemele solare au ani de lungime diferită. După un an de parlamentări federaţia a decis să ia în considerare vîrsta în Ani Galactici Standard, ceea ce a dus la un val de nemulţumiri din partea celor ce nu se descurcau cu conversiile, căci picasera bacul galactic. Aşa încît ei au atacat din nou legea, pe motiv că fiecare specie foloseşte propria bază de numeraţie, deci nu se poate defini un număr rotund. Dupa încă un an de deliberări parlamentarii au decis că un număr de ani N va fi considerat rotund dacă el se poate scrie sub forma 100...100...0 într-o bază oarecare B (exact două cifre 1, şi zero sau mai multe cifre 0).

Cîrcotasii nemaiavînd ce spune, legea a fost trecută şi a apărut impasul: numărul de cetăţeni galactici fiind foarte mare, parlamentarii nu ştiu să calculeze care vîrste sînt rotunde şi care nu, suficient de repede ca cetăţenii să primească primele înainte de obştescul lor sfîrşit.

Cerinţă

Parlamentul vă roagă pe voi să îl ajutaţi. Vîrstele cetăţenilor variază între 3 şi 2⁶⁴-1 ani, iar numărul aproximat al cetăţenilor galactici este între 1 şi 100 000. Dîndu-se numărul N al cetăţenilor precum şi fiecare vîrstă X_i, voi trebuie să calculaţi pentru fiecare X_i baza minimă în care ea este număr rotund. Dacă nu exista nici o bază, veţi afişa 0.

Date de intrare

Fişierul de intrare bonus.in conţine pe prima linie numărul N, reprezentînd numărul de cetăţeni ai galaxiei. Următoarele N linii conţin întregii X₁, X₂, ..., X_N, cîte unul pe linie.

Date de ieşire

Fişierul de ieşire bonus.out va conţine N linii. Linia i va conţine un singur număr, cea mai mică bază în care X_i este număr rotund, sau zero dacă acea bază nu există.

Restricţii

• 1 ≤ N ≤ 100,000
• pentru 20% din teste 1 ≤ N ≤ 10,000
• 3 ≤ X_i ≤ 2⁶⁴-1 pentru orice 1 ≤ i ≤ N

Exemplu