#include<iostream>
using namespace std;
int main(){
	int n,a;
	int k;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		k=0;
		cin>>a;
		if(a==1)
			cout<<k<<endl;
		else if(a==2)
			cout<<k+1<<endl;
		else if(a==3)
			cout<<k+2<<endl;
		else if(a%2==0&&a!=2)
			cout<<k+2<<endl;
		else
			cout<<k+3<<endl;
	}
	return 0;
}
		  	 				    			  					 	   		