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
#include <bits/stdc++.h>
using namespace std;

void see(int x) {cout << x;}
void see(long long int x) {cout << x;}
void see(long double x) {cout << x;}
void see(char x) {cout << '\'' << x << '\'';}
void see(string x) {cout << '\"' << x << '\"';}

template<typename T, typename V>
void see(const pair<T, V> &x) {cout << '{'; see(x.first); cout << ','; see(x.second); cout << '}';}

template<typename T>
void see(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), see(i); cout << "}";}

void _print() {cout << "]\n";}

template <typename T, typename... V>
void _print(T t, V... v) {see(t); if (sizeof...(v)) cout << ", "; _print(v...);}

#define fori(i,a,b)    for(int i=a;i<=b;i++)
#define ford(i,a,b)   for(int i=a;i>=b;i--)
#define all(a)        a.begin(), a.end()
#define in(c,x)       ((c).find(x) != (c).end())
#define isp(c,x)      (find(all(c),x) != (c).end())
#define pb             push_back
#define sz(x)          (int)x.size()
#define fill(a,v)      memset(a, v, sizeof a)
#define fs first
#define sc second
#define ub upper_bound
#define lb lower_bound
#define en '\n'
#define vt vector
#define deb(x...) cout << "[" << #x << "] = ["; _print(x)

typedef long long int lli;
typedef long double ld;
typedef list<int> li;
lli gcd(lli a,lli b){return (!b)?a:gcd(b,a%b);}



void solve(){
    lli n; cin>>n;

    if(n == 1){
        cout<<0<<en;
    } else if(n == 2){
        cout<<1<<en;
    } else if(n == 3){
        cout<<2<<en;
    } else if(n&1) {
        cout<<3<<en;
    } else {
        cout<<2<<en;
    }
}
//THINK OF SPECIAL CASES, ARRAY LIMITS, LLI vs INT, 1LL

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; cin>>t;

    while(t--)
    solve();
}