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
/*Q-1---CODEFORCES_#685(DIV-2)
Ridbit starts with an integer (n).

In one move, he can perform one of the following operations:-
1)Divide (n) by one of its proper divisors, or
2)Subtract 1 from (n) if (n) is greater than 1.

A proper divisor is a divisor of a number, excluding itself. 
For Eg-: 1,2,4,5,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-:
t=6
n=1 ---> 0
n=2 ---> 1
n=3 ---> 2
n=4 ---> 2
n=6 ---> 2
n=9 ---> 3


APPROACH-:If (n) is even then we first divide the (n) by (n/2) as (n/2) is always the proper divisor of the even 
integer, After dividing the (n) with (n/2) we will get (2) and in second step we will subtract (1) from (2) to 
obtain 1. So in TWO steps we can convert any even integer into 1.

If (n) is odd then first we will convert it into nearest even number by subtracting (1) and after that (n) will become 
even so we need two more steps to cnvert (n) into 1.
So total THREE steps are required for any odd integer to convert it into 1.

But there are some cases which do not follow the above rule; these are 1,2,3.
For (n=1) ZERO steps are required as it is already 1. 
For (n=2) we need only ONE step to convert it into (1) by subtracting 1 from 2.
For (n=3) we need only TWO steps by subtracting (1) two times from 3.
*/

//EASY QUESTION
#include <bits/stdc++.h>
#define M 1000000007
#define endl '\n'
#define ll long long
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	ll t{0};
	cin>>t;
	while(t--){
		ll n{0};
		cin>>n;

		if(n==1){
			cout<<0<<endl;
			continue;
		}

		if(n==2){
			cout<<1<<endl;
			continue;
		}

		if(n==3){
			cout<<2<<endl;
			continue;
		}

		if(n%2==0)
			cout<<2<<endl;
		else
			cout<<3<<endl;


	}
	return 0;
}