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 class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
    static class Pair
    {
        int f,s;
        char c,p;
        Pair(int f,int s,char c)
        {
            this.f=f;
            this.s=s;
            this.c=c;
        }
    }
    public static int bs(int b[],int k,int j)
    {
        if(j<0)
        return -1;
        int l=0,r=j+1;
        while(r-l>1)
        {
            int mid=(l+r)/2;
            if(b[mid]>k)
            r=mid;
            else
            l=mid;
        }
        //System.out.println(l);
        return b[l]<=k?l:-1;
    }
    public static void swapByRandom(int []arr,int n)
    {
        Random rand=new Random();
        for(int i=0;i<n;i++)
        {
            int ind=rand.nextInt(n);
            int temp=arr[i];
            arr[i]=arr[ind];
            arr[ind]=temp;
        }
    }
    static class comp implements Comparator<Pair>
    {
        public int compare(Pair p1,Pair p2)
        {
            if(p1.s==p2.s)
            return p2.f-p1.f;
            return p1.s-p2.s;
        }
    }
    static ArrayList<Integer> edge[];
    static boolean take=true;
    static int col[];
    //static ArrayList<Integer> path=new ArrayList<>();
    static int vert=-1;
    /*public static boolean dfs(int u,int par,boolean vis[])
    {
        vis[u]=true;
        for(int v:edge[u])
        {
            if(v==par)continue;
            if(!vis[v])
            {
                boolean b=dfs(v,u,vis);
                if(b)
                {
                    if(take)
                    path.add(u);
                    if(u==vert)
                    take=false;
                    return true;
                }
            }
            else
            {
                vert=v;
                path.add(u);
                return true;
            }
        }
        return false;
    }*/
    public static void main(String args[])
    {
        FastReader fs=new FastReader();
        PrintWriter pw=new PrintWriter(System.out);
        int t=fs.nextInt();
        while(t-->0)
        {
            int n=fs.nextInt();
            if(n<=2)
            pw.println(n-1);
            else if(n%2==0)
            pw.println(2);
            else
            {
                if(n==3)
                pw.println(2);
                else
                pw.println(3);
            }
        }
        pw.flush();
        pw.close();
    }
}
