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 eb emplace_back
#define pb push_back
#define INF LLONG_MAX
#define FLT_INF pow(10.0, 16)

using ll = long long;
using vll = vector<ll>;
using ull = unsigned long long;
using int2 = pair<ll, ll>;
using int3 = tuple<ll, ll, ll>;

template <typename A>
string to_string(const A &v);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return (b ? "true" : "false"); }

template <typename A, typename B>
string to_string(const pair<A, B> &p)
{
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(const tuple<A, B, C> &p)
{
  return "(" + to_string(std::get<0>(p)) + ", " + to_string(std::get<1>(p)) + ", " + to_string(std::get<2>(p)) + ")";
}

template <typename A>
string to_string(const A &v)
{
  bool first = true;
  string res = "{";
  for (const auto &x : v)
  {
    if (!first)
    {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename T>
void sort(vector<T> &val)
{
  sort(val.begin(), val.end());
}

template <typename T>
void reverse(vector<T> &val)
{
  reverse(val.begin(), val.end());
}

template <typename T>
void sort_b(vector<T> &val)
{
  sort(val.begin(), val.end(), greater<T>());
}

template <typename T>
T pair_sum(pair<T, T> &val)
{
  return val.first + val.second;
}

template <typename T>
T min(T a, T b, T c)
{
  return min(min(a, b), c);
}

template <typename T>
T max(T a, T b, T c)
{
  return max(max(a, b), c);
}

template <typename T>
T mul_mod(T a, T b, T mod)
{
  T res = 0;
  a %= mod;
  while (b)
  {
    if (b & 1)
    {
      res = (res + a) % mod;
    }
    a = (2 * a) % mod;
    b >>= 1;
  }
  return res;
}

template <typename T>
T fac_mod(T v, T mod)
{
  ll res = 1;
  for (ll i = 1; i <= v; i++)
  {
    res *= i;
    res = res % mod;
  }
  return res;
}

template <typename T>
T pow_mod(T v, T p, T mod)
{
  if (p == 1)
    return v;

  if (p % 2 == 0)
  {
    T t = pow_mod(v, p / 2, mod);
    return (t * t) % mod;
  }
  else
  {
    return (v * pow_mod(v, p - 1, mod)) % mod;
  }
}
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) ;
#endif

#define COMMON_MOD static_cast<ll>(pow(10, 9) + 7)
#define PI 3.14159265

// sort(a.begin(), a.end(), less<ll>()); greater<ll>()
// cout<<fixed<<setprecision(20)<<(s/kl)*2;
/* printf("%lld %lld \n", cur_n, m / 2 + 1);
sort(a.begin(), a.end(), [ ](ll& lhs, ll& rhs) {return abs(lhs) < abs(rhs);});
*/

class mytask
{
public:
  mytask() {}

  int solve()
  {
    ll t;
    cin >> t;
    while (t--)
    {
      ll n;
      cin >> n;
      ll res = 0;
      while (n > 1)
      {
        if (n == 2)
        {
          n--;
        }
        else if (n % 2 == 1)
        {
          n--;
        }
        else
        {
          n = 2;
        }
        res++;
      }
      cout << res << "\n";
    }
    return 0;
  }
};

int main()
{

  auto task = mytask();
  task.solve();

  return 0;
}
