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.util.Map.Entry;
import java.util.regex.Pattern;


import java.util.*;

import java.io.*;

public class Main {
	static class FastReader  extends Thread{
		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 int power(int a,int b){
		 if(b==0){
			 return 1;
		 }
		 int temp=0;
		
		 if (b%2 == 0) {
			 temp=power(a,b/2);
		 return temp*temp;
		 } 
	     else{
		   temp=power(a,b/2);
		   return a*temp*temp;
		 
		 }

		 }
	 
	
	static int binary(int a[],int start,int end,int number){
		start=0;
		end=a.length-1;
		int mid=0;

		while(start<=end){
			mid=end+(end-start)/2;
			if(a[mid]==number){
				return mid;
			}
			else
			if(a[mid]<number){
               start=mid+1;
			}
			else
			end=mid-1;
		}
		return 0;
		
	}
 
 
	static void swap(int a[], int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	static void fill(int start, int end, int a[]) {
		for (int i = 0; i < end; ++i) {
			a[i] = scan.nextInt();
		}
	}
	static int bl[]=new int[100+1];
	static void PrimeFactorisation(){
	int max=1000;
	
	for(int i=4;i<=max;i+=2){
	 bl[i]=2;//Factor of the two
	
	}
	for(int i=3;i<=Math.sqrt(max);++i){
	if(bl[i]==i){
	for(int j=i*i;j<=max;j+=i){
	if(bl[j]==j){
	bl[j]=i;
	}
	
	}
	}
	}
	}
	static void factors(int x){
	while(x!=1){
	System.out.println(bl[x]);
	x=x/bl[x];
	
	}
	}
	
	
    static FastReader sc=new FastReader();
	static FastReader scan = new FastReader();
	private static boolean add;
	static long power(long a,long b){
		return (long)(Math.log(a)/Math.log(b));
	}
	static boolean isPowerOfTwo(long n,long m)
	{
		if(n==0)
		return false;
	 
	return (int)(Math.ceil((Math.log(n) / Math.log(m)))) == 
		   (int)(Math.floor(((Math.log(n) / Math.log(m)))));
	}
	/*H.entrySet().stream().sorted(HashMap.Entry.<Long,Long>comparingByValue().reversed()).forEach(e->{
		long k=e.getKey();
		System.out.print(k+" ");
		  });;-*/
		  
	 /*static long pow(long n){

             while(n>0){
				 n>>=1;

			 }
	 }*/
	 //counting total bits
	 static long countBits(long number) 
	 {  
		   
		 // log function in base 2  
		 // take only integer part 
		 return (long)(Math.log(number) /  
					  Math.log(2) + 1); 
				
	 }
	 static int gcd(int a,int b){
		 if(b==0){
			 return a; 
		 }
		 return gcd(a,b%a);
	 }
static void reverse(char a[],int start,int end){
	while(start<=end){
	 char temp=a[start];
	 a[start]=a[end];
	 a[end]=temp;
	 ++start;
	 --end;
	}
}

static void sieve(int a[],int n){
boolean bl[]=new boolean[4000001];
bl[0]=true;
bl[1]=true;
for (int i = 2; i < bl.length; i++) {
bl[i]=false;
}
for (int i = 2; i <=Math.sqrt(10000); i++) {
if(bl[i]==false){
for (int j = i*i ;j <=10000; j=j+i) {
 bl[j]=true;

}


}
 
}

}
static int check(String num){
	int n = num.length(); 
  
   
    int sum = 0; 
    for(int i = 0; i < n; i++) 
    sum += (int)(num.charAt(i)); 

    if (sum % 3 == 0) 
        return 0; 

    if (n == 1) 
        return -1; 
  
  
    for (int i = 0; i < n; i++) 
        if (sum % 3 == (num.charAt(i) - '0') % 3) 
            return 1; 
  
  
    if (n == 2) 
        return -1; 
  
  
    return 2; 

}
static int check(Queue<Integer>I,Queue<Integer>M,int power,String m){
	int count=0;
while(M.size()!=0&&I.size()!=0){
	int start=Math.min(I.peek(),M.peek());
	int end=Math.max(I.peek(),M.peek());
	//count the sheild in between
	int shield=0;
	for(int i=start;i<=end;++i){
 if(m.charAt(i)==':')++shield;

	}
	int first=I.peek();
	int second=M.peek();

if(power-Math.abs(first-second)-shield>0){
   ++count;
   M.remove();
   I.remove();
}else{
	if(I.peek()<M.peek()){
		I.remove();
	}
	else{
		M.remove();
	}

}

	

}
return count;
          

}
static int check(TreeSet<Character>T){
	 Iterator <Character>It=T.iterator();
   String ans="";
   while(It.hasNext()){
ans+=It.next();

   }
 return ans.compareTo("acef");
}
static Node root;
static class Node{
int data;
Node left;
Node right;
Node(int data){
	this.data=data;
	
}
}
//preorder Transversal using stack
static void printt(Node root) {
	if (root == null) {
		return;
	}
	Stack<Node> S = new Stack<>();
	S.add(root);
	System.out.print(root.data + " ");
	if (root.right != null) {
		S.add(root.right);
	}
	if (root.left != null) {
		S.add(root.left);
	}
	while (S.size() != 1) {
		Node peek = S.peek();
		S.pop();
		System.out.print(peek.data + " ");
		if (peek.right != null) {
			S.add(peek.right);
		}
		if (peek.left != null) {
			S.add(peek.left);
		}

	}
}
static void check(long a){
	if(a<0)
	a=-a;

}
static int check(int a,int b){
	if(b==0){
		return 1;
	}
	int temp=1;
	 if(b%2==0){
		  temp=check(a,b/2);
		 return temp*temp;
	 }
	 else{
		 temp=check(a,b/2);
        return  a*temp*temp;
	 }

}

static void fill(){
	
}

public static void main(String[] args){
 int t=scan.nextInt();
 while(t-->0){
	 int n=scan.nextInt();
	 if(n==1){
		 System.out.println(0);
	 }
	 else
	 if(n==2){
		 System.out.println(1);
	 }
	 else
	 if(n==3){
		 System.out.println(2);
	 }
	 else{ int count=0;
		  if(n%2==1){
			  System.out.println(3);
		  }
		  else{
			  System.out.println(2);
		  }
		 
	 }
 }
   
  

  }
  

	
		
	
	


public static void gen(ArrayList<Long> a, String b){
	if((!b.isEmpty())&&Long.parseLong(b)>1e9){
		return;
	}
  
	String first=b+""+4;
	String second=b+""+7;
	a.add(Long.parseLong(first));
	a.add(Long.parseLong(second));
	gen(a,b+""+4);
	gen(a,b+""+7);
  
	
}

} 
  








 




	
	  
  



	 

	










  

 


   
  
  

