#include <bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++)
#define ll long long

//エラトステネスの篩による [1, N] の素数判定
vector<bool> primeSieve(int N) {
    vector<bool> isPrime(N+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            for (int j = 2*i; j <= N; j += i) isPrime[j] = false;
        }
    }
    return isPrime;
}

int main() {
    int B = 10'000'000;
    vector<bool> isprime = primeSieve(B);
    vector<ll> P;
    rep(i, 0, B-1) {
        if (isprime[i] and isprime[i+2]) {
            P.push_back((ll)i*(i+2));
        }
    }
    int T; cin >> T;
    while(T--) {
        ll x; cin >> x;
        auto itr = upper_bound(P.begin(), P.end(), x);
        if (itr == P.begin()) {
            cout << -1 << endl;
        }
        else cout << *prev(itr) << endl;
    }
}