[EclipsE]

Problem 2. Igra

Na papiru je napisan broj N (1 <= N <= 10^7). Dva igracha naizmenichno rade sledece: igrach koji je na potezu bira neki delilac broja koji je napisan na papiru (delilac ne sme biti 1 ili broj sa papira), racuna kolichnik broja sa papira i izabranog delioca, brise broj koji se nalazi na papriu, i pishe dobijeni kolichnik. Ukoliko igrach ne moze da odigra svoj potez (tj. jedini delioci su 1 i broj sa papira), on je pobednik. Napisati program koji treba da uchita niz brojeva i za svaki od tih brojeva odredi koji igrach pobedjuje u partiji na chijem pochetku se na papiru nalazi taj broj. Smatrati da oba igracha igraju optimalno (povlache najbolje poteze).

Ulaz. (Ulazni podaci se nalaze u datoteci igra.in) U prvom redu ulazne datoteke se nalazi broj M(5 <= M <= 20). U narednih M redova nalazi se po jedan broj N (1 <= N <= 10^7).

Izlaz. (Izlazne podatke upisati u datoteku igra.out) U izlaznu datoteku treba upisati M redova. U i-tom redu ispisati broj 1, ako prvi igrach pobedjuje kad je pochetni broj na papiru Ni, a 2, ako drugi igrach pobedjuje.

Primer 1.
igra.in
5
1
4
5
10
25

igra.out
1
2
1
2
2