igrica

Na papiru je napisan broj N (1 <= N <= 10^7). Dva igrača naizmenično rade sledeće: igrač koji je na potezu bira neki delilac broja koji je napisan na papiru (delilac ne sme biti 1 ili broj sa papira), računa količnik broja sa papira i izabranog delioca, briše broj koji se nalazi na papiru, i piše dobijeni količnik. Ukoliko igrač ne može da odigra svoj potez (tj. jedini delioci su 1 i broj sa papira), on je pobednik. Napisati program koji treba da učita niz brojeva i za svaki od tih brojeva odredi koji igrač pobeđuje u partiji na čijem početku se na papiru nalazi taj broj. Smatrati da oba igrača igraju optimalno (povlače najbolje poteze).<br><br>

Ulaz:<br>
U prvom redu se nalazi broj M (5 <= M <= 20). U narednih M redova se nalazi po jedan broj Ni (1 <= Ni <= 10^7).<br><br>

Izlaz:<br>
Na standardni izlaz treba upisati M redova. U i-tom redu ispisati broj 1, ako prvi igrač pobeđuje kada je početni broj na papiru Ni, a 2, ako drugi igrač pobeđuje.<br><br>

Input<br>
5<br>
1<br>
4<br>
5<br>
10<br>
25<br>
<br>
Output<br>
1<br>
2<br>
1<br>
2<br>
2