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

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