#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FOD(i,r,l) for (int i=r;i>=l;i--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pub push_back
#define pob pop_back
#define ii pair<int,int>
#define pll pair<long long, long long>
#define F first
#define S second
typedef unsigned long long int ull;
using namespace std;
const int N = 1e6+5;

ll n, a;
bool isPrime[N];

void sieve(){
    for(int i = 0; i <= N;++i) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i) {
         if(isPrime[i] == true) {
             for(int j = i * i; j <= N; j += i)
                 isPrime[j] = false;
        }
    }
}

void solve(){
    cin >> n;
    sieve();
    FOR(i,1,n) {
        cin >> a;
        if (isPrime[a]) {
            cout << a << '\n';
            continue;
        }
        while (!isPrime[a]) {
            if (a&1) a -= 2;
            else --a;
        }
        cout << a << '\n';
    }
}

int main(){
    fast;
    freopen("CLOPRIME.inp","r",stdin);
    freopen("CLOPRIME.out","w",stdout);
    solve();
    return 0;
}