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;
#define ll long long int
#define ld long double
#define nl '\n'
#define vi vector<ll>
#define mem(n,m) memset(n,m,sizeof(n))
#define pii pair<int,int>
#define tiii tuple<int, int, int>
#define pll pair<ll,ll>
#define sii set<int>
#define sll set<ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fs first
#define se second
#define eb emplace_back
#define emp emplace
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define mod 1e9 + 7
#define all(c) c.begin(), c.end()
#define rall(v) v.rbegin(), v.rend()
#define io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define fr(i,n) for(int i=0;i<n;i++)
#define rfr(i,n) for(int i=n-1;i>=0;i--)
#define rep(a,b,c) for(int a=b;a<c;a++)
#define repr(a,b,c) for(int a=b;a>c;a--)
#define pi acos(-1)
#define inf 1e16
#define mod 1e9 + 7
ll gcd(ll a,ll b)
{ if (b == 0) return a;return gcd(b, a % b);}
ll lcm(ll a,ll b)
{ return a*b/gcd(a,b);}


int main()
{
    io;
    ll t;
    cin>>t;
    //t=1;
    while(t--)
    {
        ll n;
        cin>>n;
        if(n==1 ||n==2 || n==3)
            cout<<n-1<<nl;
        else if(n%2==0)
            cout<<"2"<<nl;
        else
            cout<<"3"<<nl;
    }

    return 0;
}
