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>

/*#include<iostream>
#include<vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/
//using namespace __gnu_pbds;

#define PB push_back
using namespace std;
#define N 400000;
#define loop(i , x , n) for(ll i = x;i< n;i++)
#define loopr(i , x , n) for(ll i = n;i>=x ;i--)
#define mod 998244353
#define ll long long
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef pair<ll, ll> pll;
#define mp(x, y) make_pair<long long , long long >(x, y)
#define SIN(x) sin(x * 3.141592653589793238)
#define COS(x) cos(x * 3.141592653589793238)
#define endl "\n"
#define ff first
#define ss second
#define ELGO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define tc ll tc; cin>>tc; while(tc--)
#define vv(x) vector<x>
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof  pop_front
#define endl "\n"
#define umap unordered_map
//#define pq priority_queue
#define ca(a,n) for(ll i=0;i<n;i++){ cin>>a[i]; }
#define ca1(a,n) for(ll i=1;i<=n;i++){ cin>>a[i]; }
#define svec(x) sort(x.begin(), x.end())
#define rsvec(x) sort(x.begin(), x.end(), greater<ll>())
#define all(x) (x).begin(), (x).end()
const int INF = 1e9;
ll arr[400000];
ll ans ;

 void solve(){
    ll n, k  ;
    cin>>n;

    if( n==1){
        cout<< 0<< endl;return;
    }
    if( n==2){
        cout<<1<<endl;
        return;
    }
    if( n%2 == 0  || n== 3){
        cout<< 2 << endl;
        return ;
    }
    cout<< 3<< endl;
    return;





}





int main()
{
    ELGO;
tc{
solve();
}




}
