Ridbit starts with an integer n.

In one move, he can perform one of the following operations: 

  * divide n by one of its proper divisors, or 
  * subtract 1 from n if n is greater than 1. 



A proper divisor is a divisor of a number, excluding itself. For example, 1, 2, 4, 5, and 10 are proper divisors of 20, but 20 itself is not.

What is the minimum number of moves Ridbit is required to make to reduce n to 1?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The only line of each test case contains a single integer n (1 ≤ n ≤ 10^9).

Output

For each test case, output the minimum number of moves required to reduce n to 1.

Example

Input


6
1
2
3
4
6
9


Output


0
1
2
2
2
3

Note

For the test cases in the example, n may be reduced to 1 using the following operations in sequence

1

2 \xrightarrow{} 1

3 \xrightarrow{} 2 \xrightarrow{} 1

4 \xrightarrow{} 2 \xrightarrow{} 1

6 \xrightarrow{} 2 \xrightarrow{} 1

9 \xrightarrow{} 3 \xrightarrow{} 2\xrightarrow{} 1
import java.util.*;
import java.io.*;

public class Main {
    static Scanner sc;
    static BufferedReader br;
    static PrintWriter out;

    public static void main(String[] args) throws Exception{
        sc = new Scanner(System.in);
        //   br=new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);

        int t = 1;
        // t = Integer.valueOf(br.readLine().split(" ")[0]);
        //seiveOfEri();
        t=sc.nextInt();

        while (t-- > 0) {
            forEachTestCase();
        }


        //   br.close();
        sc.close();
        out.close();
    }

    static void forEachTestCase() throws  Exception{
        int n=sc.nextInt();
        if(n==1){
            out.println(0);
        }
        else if(n==2 ){
            out.println(1);
        }
        else if(n%2==0 || n==3){
            out.println(2);
        }
        else{
            out.println(3);
        }
    }

    static void remove(TreeMap<Integer,Integer> tm,int key){
        int fre=tm.get(key);
        if(fre==1){
            tm.remove(key);
            return;
        }
        tm.put(key,fre-1);
    }
    static long mod = 998244353;


    static long[][] mul(long a[][],long b[][]){
        long ans[][]=new long[a.length][b[0].length];
        for (int i = 0; i <a.length ; i++) {
            for (int j = 0; j <b[0].length ; j++) {
                for (int k = 0; k <a[0].length ; k++) {
                    ans[i][j]=add(ans[i][j],mul(a[i][k],b[k][j]));
                }
            }
        }
        return ans;
    }
    static long add(long a, long b) {
        a %= mod;
        b %= mod;
        return (a + b) % mod;
    }

    static long mul(long a, long b) {
        a %= mod;
        b %= mod;
        return (a * b) % mod;
    }

    static long sub(long a, long b) {
        a %= mod;
        b %= mod;
        return (((a - b) % mod) + mod) % mod;
    }

    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    static int gcd(int a,int b){
        if(b==0)return a;
        return gcd(b,a%b);
    }

    static long modPow(long a, long b) {
        long ans = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                ans = mul(ans, a);
            }
            a = mul(a, a);
            b >>= 1;
        }
        return ans;
    }

    static long modInv(long a) {
        return modPow(a, mod - 2);
    }

    static long fact[],ifact[];
    static int maxFactSize=200001;
    static void  initFact(){
        fact=new long[maxFactSize];
        ifact=new long[maxFactSize];
        fact[0]=ifact[0]=1;
        for (int i = 1; i <maxFactSize ; i++) {
            fact[i]=mul(fact[i-1],i);
            ifact[i]=mul(ifact[i-1],modInv(i));
        }
    }

    static long nCr(int n,int r){
        if(n>r || n<0 || r<0)return 0;
        if(fact==null)initFact();
        return mul(fact[n],mul(ifact[n],ifact[r]));
    }

    static int seive[];
    static ArrayList<Integer> primes;
    static int seiveLength=2000001;
    static void seiveOfEri(){
        seive=new int[seiveLength];
        primes=new ArrayList<>();
        for (int i = 2; i <seiveLength ; i++) {
            if(seive[i]==0) {
                primes.add(i);
                for (int j = i; j < seiveLength; j += i) {
                    seive[j]=i;
                }
            }
        }
    }



    static class DSU{
        int n,par[],size[],connectedComponent;
        DSU(int n){
            this.n=n;
            par=new int[n];
            size=new int[n];
            connectedComponent=n;
            for(int i=0;i<n;i++){
                par[i]=i;
                size[i]=1;
            }
        }
        int root(int u){
            if(u==par[u]){
                return u;
            }
            return par[u]=root(par[u]);
        }
        boolean isConnected(int u,int v){
            u=root(u);
            v=root(v);
            if(u==v)return true;
            return false;
        }
        void union(int u,int v){
            u=root(u);
            v=root(v);
            if(u!=v){
                if(size[u]<size[v]){
                    int temp=u;
                    u=v;
                    v=temp;
                }
                size[u]+=size[v];
                par[v]=u;
                connectedComponent--;
            }
        }
        boolean oneComponent(){
            if(connectedComponent==1)return true;
            return false;
        }
    }

//    class SegmentTree{
//        class Node{
//           //update this
//        }
//        Node tree[];
//        SegmentTree(int n){
//            tree=new Node[4*n];
//        }
//        void update(int cur,int l,int r,int ind,int val){
//            if(l==r){
//                //update this
//                tree[cur]=new Node();
//                return;
//            }
//            int mid=(l+r)>>1;
//            if(mid>=ind)update(2*cur+1,l,mid,ind,val);
//            else update(2*cur+2,mid+1,r,ind,val);
//            tree[cur]=merge(tree[2*cur+1],tree[2*cur+2]);
//        }
//        Node merge(Node o1,Node o2){
//            //update this
//        }
//        Node query(int cur,int l,int r,int start,int end){
//            //update this
//            if(l>end || r<start)return new Node();
//            if(l>=start && r<=end)return tree[cur];
//            int mid=(l+r)>>1;
//            return merge(query(2*cur+1,l,mid,start,end),query(2*cur+2,mid+1,r,start,end));
//        }
//    }
}
