#include<bits/stdc++.h>

using namespace std;


int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int count=0;
		while(n>1){
			bool flag=true;
			for(int i=2;i<=sqrt(n);i++){
				if(n%i==0){
					flag=false;
					n=i;
					break;
				}
			}
			if(flag==true){
				n=n-1;
			}
			count++;
			
		}
		cout<<min(count,3)<<endl;
	}
}