#include<bits/stdc++.h>
using namespace std;

int smallestDivisor(int n) {
    if (n % 2 == 0) 
        return 2; 
    for (int i = 3; i*i <= n; i += 2) { 
        if (n % i == 0) 
            return i; 
    } 
    return n; 
} 

int func(int x){
	int ans = 0;
	while(x > 1){
		int y = smallestDivisor(x);
		if(y == x){
			x--;
		}
		else{
			x = y;
		}
		ans++;
	}
	if(ans > 3) return 3;
	return ans;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		int x;
		cin>>x;
		cout<<func(x)<<endl;
	}
	return 0;
}