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 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).

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 se nalazi po jedan broj N_i (1 ≤ N_i ≤ 10⁷).

Izlaz:

(Izlazne podatke upisati u datoteku igra.out) U izlaznu datoteku treba upisati M redova. U i-tom redu ispisati broj 1, ako prvi igrač pobeđuje kad je početni broj na papiru N_i, a 2, ako drugi igrač pobeđuje.

Primer 1:

5
1
4
5
10
25

1
2
1
2
2

#include <iostream>
#include <cstdio>
using namespace std;


int Solve(int n){
  int cnt = 0;
    
  for (long k = 2; cnt <= 2 && 2 * k <= n; k++){
    long tmp = n;
    while (tmp % k == 0){
      cnt++;
      tmp /= k;
    }
  }
  if (cnt == 2) return 2;
  else return 1;
}
  
int main(){
  FILE *f, *fout;
  f = fopen("igra.in", "r");
  fout = fopen("igra.out", "w");
  
  int test;
  fscanf(f, "%ld", &test);
  for (int i = 0; i < test; i++){
    int n;
    fscanf(f, "%ld", &n);
    fprintf(fout, "%ld\n", Solve(n));
  }
  
  fclose(f); fclose(fout);
  return 0;
}