#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> dp(101), tb(101, 1);
    dp[1] = 1, dp[2] = 2;
    for(int j = 2; j <= 100; j++){
        for(int k = j; k <= 100; k += j){
            tb[k]++;
        }
    }
    for(int i = 3; i <= 100; i++)dp[i] = dp[i - tb[i]];
    int Q, N;
    cin >> Q;
    while(Q--){
        cin >> N;
        cout << (N <= 100 ? dp[N] : 2) << '\n';
    }
}