#include <iostream>
#include <math.h>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    map<int, int>MAP;
    for (int i = 0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        if (MAP[tmp] == 0)
        {
            if (tmp % 3 == 0 && tmp % 2 == 0) MAP[tmp] = 1;
            else if (tmp % 2 != 0 && tmp % 3 != 0) MAP[tmp] = 2;
            else if (pow(int(sqrt(tmp)), 2) == tmp || (tmp % 7 != 0 && tmp % 2 == 0)) MAP[tmp] = 3;
            else MAP[tmp] = -1;
        }
        if (MAP[tmp] == -1) cout << "0 ";
        else cout << MAP[tmp] << " ";
    }
}

//ZeroJudge N361
//Dr. SeanXD