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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Random;

public class Problem {
	static class Erickde {
		private int BS = 1 << 16;

		private char NC = (char) 0;
		private byte[] buf = new byte[BS];
		private int bId = 0, size = 0;
		private char c = NC;
		private double cnt = 1;
		private BufferedInputStream in;

		public Erickde() {
			in = new BufferedInputStream(System.in, BS);
		}

		public Erickde(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			} catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		private char getChar() {
			while (bId == size) {
				try {
					size = in.read(buf);
				} catch (Exception e) {
					return NC;
				}
				if (size == -1)
					return NC;
				bId = 0;
			}
			return (char) buf[bId++];
		}

		public int nextInt() {
			return (int) nextLong();
		}

		public int[] nextInts(int N) {
			int[] res = new int[N];
			for (int i = 0; i < N; i++) {
				res[i] = (int) nextLong();
			}
			return res;
		}

		public long[] nextLongs(int N) {
			long[] res = new long[N];
			for (int i = 0; i < N; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long nextLong() {
			cnt = 1;
			boolean neg = false;
			if (c == NC)
				c = getChar();
			for (; (c < '0' || c > '9'); c = getChar()) {
				if (c == '-')
					neg = true;
			}
			long res = 0;
			for (; c >= '0' && c <= '9'; c = getChar()) {
				res = (res << 3) + (res << 1) + c - '0';
				cnt *= 10;
			}
			return neg ? -res : res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c != '.' ? cur : cur + nextLong() / cnt;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while (c <= 32)
				c = getChar();
			while (c > 32) {
				res.append(c);
				c = getChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while (c <= 32)
				c = getChar();
			while (c != '\n') {
				res.append(c);
				c = getChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if (c > 32)
				return true;
			while (true) {
				c = getChar();
				if (c == NC)
					return false;
				else if (c > 32)
					return true;
			}
		}
	}

	public static void quicksort(int[] a) {
		if (a == null)
			return;
		quicksort(a, 0, a.length - 1);
	}

	private static void quicksort(int[] a, int lo, int hi) {
		if (lo < hi) {
			int splitPoint = partition(a, lo, hi);
			quicksort(a, lo, splitPoint);
			quicksort(a, splitPoint + 1, hi);
		}
	}

	private static final double EPS = 0.00000001;

	private static int partition(int[] a, int lo, int hi) {
		int pivot = a[lo];
		int i = lo - 1, j = hi + 1;
		while (true) {
			do {
				i++;
			} while (a[i] < pivot);
			do {
				j--;
			} while (a[j] > pivot);
			if (i < j)
				swap(a, i, j);
			else
				return j;
		}
	}

	static int binarySearch(int arr[], int l, int r, int x) {
		if (r >= l) {
			int mid = l + (r - l) / 2;

			if (arr[mid] == x)
				return mid;

			if (arr[mid] > x)
				return binarySearch(arr, l, mid - 1, x);

			return binarySearch(arr, mid + 1, r, x);
		}

		return -1;
	}

	private static void swap(int[] ar, int i, int j) {
		int tmp = ar[i];
		ar[i] = ar[j];
		ar[j] = tmp;
	}

	static Random RANDOM = new Random();

	static int randInt(int min, int max) {
		return RANDOM.nextInt((max - min) + 1) + min;
	}

	public static int findMaxGCD(int arr[], int n) {

		int high = 0;
		for (int i = 0; i < n; i++)
			high = Math.max(high, arr[i]);

		int divisors[] = new int[high + 1];

		for (int i = 0; i < n; i++) {

			for (int j = 1; j <= Math.sqrt(arr[i]); j++) {

				if (arr[i] % j == 0) {

					divisors[j]++;

					if (j != arr[i] / j)
						divisors[arr[i] / j]++;
				}
			}
		}

		for (int i = high; i >= 1; i--)

			if (divisors[i] > 1)
				return i;
		return 1;
	}

	static int arraySortedOrNot(int arr[], int n) {

		if (n == 1 || n == 0)
			return 1;

		if (arr[n - 1] < arr[n - 2])
			return 0;

		return arraySortedOrNot(arr, n - 1);
	}

	static boolean isPrime(int n) {

		if (n <= 1)
			return false;

		else if (n == 2)
			return true;

		else if (n % 2 == 0)
			return false;

		for (int i = 3; i <= Math.sqrt(n); i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}

	public static void main(String[] args) throws Exception {
		Erickde scan = new Erickde();
		PrintWriter out = new PrintWriter(System.out);
		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 % 2 == 0) {
				System.out.println(2);
			}else if (n==3) {
				System.out.println(2);
			} else {
				System.out.println(3);

			}
		}

	}
}