Fișierul intrare/ieșire	bonus.in, bonus.out	Sursă	RMI 2016
Autor	Cristian Frâncu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	512 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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