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 Solution {
    static Scanner in =new Scanner(System.in);
    static final Random random=new Random();
    static int mod=1000_000_007;
    public static void main(String[] args) {
      int tt=in.nextInt();in.nextLine();
       outer: while(tt-->0){
           int n=in.nextInt();long res=0;
           //int a[]=readAr(n);
           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==1){
               System.out.println(3);continue outer;
           }
           if(n%2==0){
               System.out.println(2);continue outer;
           }
           //System.out.println(res);
      } 
    }
    static int nCr(int n,int r,int p){
        if (r == 0) return 1; 
        if(r==1)return n;
        return ((int)fact(n)*modInverse((int)fact(r),p)%p * modInverse((int)fact(n-r),p) % p)%p; 
    }
    static int modInverse(int n, int p) { 
        return power(n, p - 2, p); 
    } 
    static int power(int x,int y,int p) { 
        int res = 1;
        x= x % p;
        while (y>0) {
            if (y%2==1) 
                res= (res *x)% p;
            y= y >> 1;
            x= (x * x)% p; 
        }
        return res; 
    } 
    static int find(int p){
        int m=0;int l=0,r=p;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(mid!=r)m++;
            if(mid==r)break;
            if(mid<r)l=mid+1;
        }return m;
    }
    static int[]readAr(int n) {
        int[] a=new int[n];
        for (int i=0; i<n; i++) {a[i]=in.nextInt();}
        return a;
	}
    static int fact(int k){
        long[]f=new long[10001];f[1]=1;
        for(int i=2;i<10001;i++){
            f[i]=(i*f[i-1]% mod);
        }
        return (int)f[k];
    }
	static void ruffleSort(int[] a) {
		int n=a.length;
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	static void reverse(int []a){
        int n= a.length;
        for(int i=0;i<n/2;i++){
            int temp=a[i];
            a[i]=a[n-i-1];
            a[n-i-1]=temp;
            a[i]=-a[i];
        }
        debug(a);
	}
	static void debug(int []a) {
        for (int i=0; i<a.length;i++) System.out.print(a[i]+" ");
	}
	static void print(List<Integer>s) {
        for(int x:s) System.out.print(x+",");
        System.out.println();
	}
	static int gcd(int a, int b) {
        return b==0 ? a : gcd(b, a % b);
	}
    static int find_max(int []a){
        int m=Integer.MIN_VALUE;
        for(int x:a)m=Math.max(x,m);
        return m;
    }
    static int find_min(int []a){
        int m=Integer.MAX_VALUE;
        for(int x:a)m=Math.min(x,m);
        return m;
    }
}