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.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.util.InputMismatchException;
public class A
{
    public static void solve()
    {
        int t=sc.nextInt();
        while (t-->0)
        {
           int n=sc.nextInt();
           int ans2=1;
           if (n==1) out.println(0);
           else if (n==2) out.println(1);
           else if (n==3) out.println(2);
           else if (n%2!=0)
           {
        	   out.println(3);
           }
           else
           {
        	   out.println(2);
           }
        }
    }
    public static void main(String[] args) 
    {
        new Thread(null, null, "Thread", 1 << 27) 
        {
            public void run() 
            {
                try 
                {
                    out = new PrintWriter(new BufferedOutputStream(System.out));
                    sc = new FastReader(System.in);
                    solve();
                    out.close();
                } 
                catch (Exception e) 
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }
                .start();
    }
    public static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> 
    {
        public U x;
        public V y;
    
        public Pair(U x, V y) 
        {
            this.x = x;
            this.y = y;
        }
    
        public int hashCode() 
        {
            return (x == null ? 0 : x.hashCode() * 31) + (y == null ? 0 : y.hashCode());
        }
    
        public boolean equals(Object o) 
        {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (x == null ? p.x == null : x.equals(p.x)) && (y == null ? p.y == null : y.equals(p.y));
        }
    
        public int compareTo(Pair<U, V> b) {
            int cmpU = x.compareTo(b.x);
            return cmpU != 0 ? cmpU : y.compareTo(b.y);
        }
    
        public String toString() {
            return String.format("(%s, %s)", x.toString(), y.toString());
        }
    
    }
    static final Random random=new Random();
    static int max(int[] arr)
    {
    	int m=Integer.MIN_VALUE;
    	for (int i=0;i<arr.length;i++)
    	{
    		m=Math.max(arr[i], m);
    	}
    	return m;
    }
    static int min(int[] arr)
    {
    	int m=Integer.MAX_VALUE;
    	for (int i=0;i<arr.length;i++)
    	{
    		m=Math.min(arr[i], m);
    	}
    	return m;
    }
    static int gcd(int a,int b)
    {
        if (b==a)
            return a;
        return gcd(b,a%b);
    }
    static void UjjwalSort(int[] a) 
    {
        int n=a.length;//shuffle, then sort 
        for (int i=0; i<n; i++) 
        {
            int ujjwal=random.nextInt(n), temp=a[ujjwal];
            a[ujjwal]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
    public static PrintWriter out;
    public static FastReader sc;
    public static class FastReader 
    {
        private InputStream stream;
        private byte[] buf = new byte[4096];
        private int curChar, snumChars;
        public FastReader(InputStream stream) 
        {
            this.stream = stream;
        }
        public int read() 
        {
            if (snumChars == -1) 
            {
                throw new InputMismatchException();
            }
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                catch (IOException E) 
                {
                    throw new InputMismatchException();
                }
            }
            if (snumChars <= 0) 
            {
                return -1;
            }
            return buf[curChar++];
        }
        public int nextInt() 
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            int number = 0;
            do 
            {
                number *= 10;
                number += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return number * sgn;
        }
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            long sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            long number = 0;
            do 
            {
                number *= 10L;
                number += (long) (c - '0');
                c = read();
            } while (!isSpaceChar(c));
            return number * sgn;
        }
        public int[] nextIntArray(int n) 
        {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) 
            {
                arr[i] = this.nextInt();
            }
            return arr;
        }
        public long[] nextLongArray(int n) 
        {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) 
            {
                arr[i] = this.nextLong();
            }
            return arr;
        }
        public String next()
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public String nextLine() 
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do
            {
                res.appendCodePoint(c);
                c = read();	
            } while (!isEndofLine(c));
            return res.toString();
        }
        public boolean isSpaceChar(int c)
        {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        public boolean isEndofLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
}
