#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

//#ifndef DLOCAL
//   #define cin fin
//   #define cout fout
//   ifstream cin(".in");
//   ofstream cout(".out");
//#endif

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e7 + 5;
bitset<nmax> ciur;

int start(int n) {
   n = -n;   
   int j, R = nmax * 2;
   for(j = n + 1; ciur[j] == 1; j++) {
      if(ciur[j * 2 + 1] == 0) R = min(R, 2 * j + 1);
   }
   R = min(R, 2 * j);
   return R;
}

void testcase() {
   int n;
   cin >> n;
   if(n == 0) {
      cout << 3 << '\n';
   }
   if(n > 0) {
      if(ciur[n] == 0) cout << 1 << '\n';
      else if(ciur[n * 2 - 1] == 0) cout << 2 << '\n';
      else if(ciur[n * 2 + 1] == 0) cout << 2 << '\n';
      else {
         int R = start(-n);
         for(int i = n + 1; i * 2 + 2 < R; i++) R = min(R, start(-i));
         cout << R << '\n';
      }
   }
   if(n < 0) {
      n = -n;
      int R = start(-n);
      for(int i = n + 1; i * 2 + 2 < R; i++) R = min(R, start(-i));
      cout << R << '\n';
   }
}

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   ciur[0] = ciur[1] = 1;
   for(int i = 2; i < nmax; i++) {
      if(ciur[i] == 0) {
         for(ll j = (ll)i * i; j < nmax; j += i) ciur[j] = 1;
      }
   }
   
   int T;
   cin >> T;
   while(T--) testcase();
   
}

/**
      Ovaj podrum ima hladan sjaj\Iako je to bolje od gomile drugih
--
*/