Na papiru je napisan broj N (1 ≤ N ≤ 10⁷). 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 biti1 ili broj sa papira), računa količnik broja sa papira i izabranog delioca, briše brojkoji se nalazi na papiru, i piše dobijeni količnik. Ukoliko igrač ne može da odigra svojpotez (tj. jedini delioci su 1 i broj sa papira), on je pobednik. Napisati program kojitreba da učita niz brojeva i za svaki od tih brojeva odredi koji igrač pobeđuje u partijina čijem početku se na papiru nalazi taj broj. Smatrati da oba igrača igraju optimalno(povlače najbolje poteze).

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke se nalazibroj M (5 ≤ M ≤ 20). U narednih M redova se nalazi po jedan broj N_i (1 ≤ N_i ≤ 10⁷).

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U izlaznu datoteku treba upisatiM redova. U i-tom redu ispisati broj 1, ako prvi igrač pobeđuje kad je početni broj napapiru N_i, a 2, ako drugi igrač pobeđuje.

Primer 1:

5
1
4
5
10
25

1
2
1
2
2