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.*;
	import java.math.*;
	public class A
	
	{ 
		 static FastReader sc=new FastReader(); 
		 
			  public static void main(String[] args) 
	    {
				  //StringBuffer sb=new StringBuffer("");
				  int ttt=1;
				     ttt =i(); 
			        outer :while (ttt-- > 0) 
					{
			        	  
			        	int n=i();
			        	if(n==1) {
			        		System.out.println("0");
			        		continue outer;
			        	}
			        	if(n==2) {
			        		System.out.println("1");
			        		continue outer;
			        	}
			        	if(n==3) {
			        		System.out.println("2");
			        		continue outer;
			        	}
			        	if(n%2==0) {
			        		System.out.println("2");
			        		continue outer;
			        	}
			        	System.out.println("3");
			        	
			        	
					}
			       // System.out.println(sb.toString());
	    }
			
			
	static int[] input(int n) {
		int A[]=new int[n];
		   for(int i=0;i<n;i++) {
			   A[i]=sc.nextInt();
		   }
		   return A;
	   }
	static long[] inputL(int n) {
		long A[]=new long[n];
		   for(int i=0;i<n;i++) {
			   A[i]=sc.nextLong();
		   }
		   return A;
	   }
	static String[] inputS(int n) {
		String A[]=new String[n];
		   for(int i=0;i<n;i++) {
			   A[i]=sc.next();
		   }
		   return A;
	   }
	
	
	static void input(int A[],int B[]) {
		   for(int i=0;i<A.length;i++) {
			   A[i]=sc.nextInt();
			   B[i]=sc.nextInt();
		   }
	}
	static int max(int A[]) {
		int max=Integer.MIN_VALUE;
		for(int i=0;i<A.length;i++) {
			max=Math.max(max, A[i]);
		}
		return max;
	}
	static int min(int A[]) {
		int min=Integer.MAX_VALUE;
		for(int i=0;i<A.length;i++) {
			min=Math.min(min, A[i]);
		}
		return min;
	}
	static long max(long A[]) {
		long max=Long.MIN_VALUE;
		for(int i=0;i<A.length;i++) {
			max=Math.max(max, A[i]);
		}
		return max;
	}
	static long min(long A[]) {
		long min=Long.MAX_VALUE;
		for(int i=0;i<A.length;i++) {
			min=Math.min(min, A[i]);
		}
		return min;
	}
	static long mod(long x) {
		 int mod=1000000007;
		  return ((x%mod + mod)%mod);
	}
	
	     static int i() {
	    	 return sc.nextInt();
	     }
	     static String s() {
	    	 return sc.next();
	     }
	     static long l() {
	    	 return sc.nextLong();
	     }  
	     static void sort(int[] A){
	        int n = A.length;
	        Random rnd = new Random();
	        for(int i=0; i<n; ++i){
	            int tmp = A[i];
	            int randomPos = i + rnd.nextInt(n-i);
	            A[i] = A[randomPos];
	            A[randomPos] = tmp;
	        }
	        Arrays.sort(A);
	     }
	     static boolean prime(int n) 
		    { 
		        if (n <= 1) 
		            return false; 
		        if (n <= 3) 
		            return true; 
		        if (n % 2 == 0 || n % 3 == 0) 
		            return false; 
		        double sq=Math.sqrt(n);
		  
		        for (int i = 5; i <= sq; i = i + 6) 
		            if (n % i == 0 || n % (i + 2) == 0) 
		                return false; 
		        return true; 
		    } 
	     static int gcd(int a, int b) 
	     { 
	         if (a == 0) 
	             return b; 
	         return gcd(b % a, a); 
	     } 
	  
	        
	        
	    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; 
	        } 
	    } 
	} 
	
	
	
