#include #include #include #include using namespace std; using ll = long long; const ll MAX = 1e7; vector sieve(MAX + 1, true); vector L; int main() { sieve[0] = sieve[1] = false; for (ll i = 2; i <= sqrt(MAX); ++i) { if (sieve[i]) { for (ll j = i * i; j <= MAX; j += i) { sieve[j] = false; } } } // Lを作る: 素数pで、p+2も素数であるものを保存 for (ll i = 2; i <= MAX - 2; ++i) { if (sieve[i] && sieve[i + 2]) { L.push_back(i); } } ll T; cin >> T; while (T--) { ll N; cin >> N; ll rootN = sqrt(N); auto it = upper_bound(L.begin(), L.end(), rootN); if (it != L.begin()) --it; // upper_boundなので一つ前に戻す while (it != L.begin() && (*it) * (*it + 2) > N) { --it; } if ((*it) * (*it + 2) > N) { cout << -1 << endl; } else { cout << (*it) * (*it + 2) << endl; } } return 0; }