 //বিসমিল্লাহির_রহমানির_রহীম
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI acos(-1.0)
#define N 2000015
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define CASES int t;cin>>t;for(int T=1;T<=t;T++)
#define F first
#define S second
#define pb push_back
#define f(n) for(int i = 1; i <= n; i++)
#define print(x) cout << x << endl
#define sprint(x) cout << x << " "
#define in1(a) cin >> a
#define in2(a,b) cin >> a >> b
#define in3(a,b,c) cin >> a >> b >> c
#define in4(a,b,c,d) cin >> a >> b >> c >> d
///A
bool p(ll n)
{
    for(ll i = 2; i <= sqrt(n); i++)
        if(n%i == 0)
            return false;
    return true;
}
int main()
{
    CASES
    {
        ll n;
        in1(n);
        set < ll > st;
        vector < ll > v;
        if(n == 1)
        {
            print(0);
            continue;
        }
        if(n == 2)
            print(1);
        else if(n == 3)
            print(2);
        else if((p(n) || n & 1))
            print(3);
        else if(n%2 == 0)
            print(2);
    }
}
