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 <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <vector>
#include <queue>

#define ll long long
#define dd long double
#define ff first
#define ss second
#define cini(n) int n; cin>>n;
#define cinl(n) long long n; cin>>n;
#define cins(s) string s; cin>>s;
#define vecti(v) vector<int> v(n);
#define vectl(v) vector<long long> v;
#define vects(s) vector<string> v;
#define all(v) v.begin(), v.end()
#define upi(init, n) for(ll i = init; i < n; ++i)
#define upj(init, n) for(ll j = init; j < n; ++j)
#define upk(init, n) for(ll k = init; k < n; ++k)
#define upl(init, n) for(ll l = init; l < n; ++l)
#define upm(init, n) for(ll m = init; m < n; ++m)
#define downi(init, n) for(ll i = init; i > n; --i)
#define downj(init, n) for(ll j = init; j > n; --j)
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define el "\n"
#define PI 3.1415926535897932384626433832795
#define eps 0.0000000000001

using namespace std;

ll gcd(ll a, ll b)
{
    if(a%b==0)
        return b;
    else
        return gcd(b,a%b);
}

ll lcm(ll a, ll b)
{
    ll temp = a * b;
    temp /= gcd(max(a,b), min(a,b));
    return temp;
}

int bsearch(ll arr[], ll req, int n)
{
    sort(arr,arr+n);
    int start = 0, end = n-1;
    while(start <= end)
    {
        int temp = start + end;
        temp /=2;
        if(arr[temp]>req)
            end = temp-1;
        if(arr[temp]<req)
            start = temp+1;
        if(arr[temp]==req)
            return temp;
    }
    return -1;
}

ll fastpower(ll a, ll b)
{
    ll res = 1;
    while(b>0)
    {
        if(b & 1)
        {
            res = res*a;
        }
        b /= 2;
        a = a * a;
    }
    return res;
}

int main()
{

  	#ifndef ONLINE_JUDGE
	   	  freopen("input.txt", "r", stdin);
		  freopen("output.txt", "w", stdout);
    #endif

  	ios_base::sync_with_stdio(false);
    cin.tie(0);


    cini(tc);
    while(tc--)
    {
        cini(n);
        if(n==1)
            cout<<0<<el;
        else if(n==2)
            cout<<1<<el;
        else if(n==3)
            cout<<2<<el;
        else
        {
            if(n%2==0)
                cout<<2<<el;
            else
                cout<<3<<el;
        }
    }



}