#include <iostream>
#include <cstdio>
#include <climits>
#include <cmath>
using namespace std;
typedef __int64 ll;
const int INF = LONG_MAX;
bool ok(ll x)
{
  if (x * x < 2) return false;
  if (x <= 0) return false;
  for (ll i = 2; i * i <= x; i++) {
    if (x % (i * i) == 0) {
      return false;
    }
  }
  return true;
}
void solve()
{
  ll x;
  cin >> x;
  ll t = sqrt(x);
  ll ans = INF;
  if (ok(t)) {
    ans = x - t * t;
    if (ans < 0) ans = -ans;
  }
  ll rr = INF;
  for (ll i = 1; ;i++) {
    if (ok(t + i)) {
      rr = t + i;
      break;
    }
  }
  ll ans1 = rr * rr - x;
  ll ans2 = INF;
  if (ans1 < 0) ans1 = -ans1;
  ll l = INF;
  for (ll i = 1; ;i++) {
    if ((t - i) * (t - i) < 2) break;
    if (x - (t - i) * (t - i) > ans1) break;
    if (ok(t - i)) {
      ans2 = x - (t - i) * (t - i);
    }
  }
  ans1 = min(ans1, ans2);
  ans = min(ans1, ans);
  cout << ans << endl;
}
int main()
{
    //freopen("in.txt", "r", stdin);
  //freopen("in2.txt", "r", stdin);
  int t = 1;
  scanf("%d", &t);
  while (t--) {
      solve();
    }
}