#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;

    while(t--){
        int n;
        cin>>n;

        int count=0;

        while(n!=1){
            if(n==2){
                n=1;
                count++;
                continue;
            }

            if(n==3){
                n=2;
                count++;
                continue;
            }

            if(n%2==0){
                n=2;
                count++;
                continue;
            }

            if(n%3==0){
                n=3;
                count++;
                continue;
            }

            else{
                n--;
                count++;
            }
        }

        cout<<count<<endl;
    }
}
