/* Courtesy: TopCoder Algorithm Tutorials on Primality Testing: Non Deterministic Algorithms */

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<climits>
#include<vector>
#include<iterator>
#include<set>
#include<bitset>
#include<ctime>

#define fr(i,a,b) for(int i=a; i<b; i++)
#define s(a) scanf("%d", &a)
#define sl(a) scanf("%lld", &a)
#define p(a) printf("%d\n", a)
#define w(t) while(t--)
#define pb push_back
#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;

typedef long long int lli;
typedef vector<int> VI;
typedef vector<string> VS;

lli mulmod(lli a, lli b, lli c) {
    lli x = 0, y = a%c;
    while(b > 0) {
        if(b%2) x = (x+y)%c;
        y = (y<<1)%c;
        b >>= 1;
    }
    return x%c;
}

lli modulo(lli a, lli b, lli c) {
    lli x=1, y=a;
    while(b > 0) {
        if(b%2) x = mulmod(x, y, c);
        //x=(x*y)%c;
        y = mulmod(y, y, c);
        //y = (y*y)%c;
        b >>= 1;
    }
    return x%c;
}

bool Miller(lli p, int iteration) {
    if(p<2)                 return false;
    if(p!=2 && p%2==0)          return false;
    lli s=p-1;
    while(s%2==0)   s >>= 1;
    fr(i,0,iteration) {
        lli a = rand()%(p-1) + 1, temp = s;
        lli mod = modulo(a, temp, p);
        while(temp != p-1 && mod != 1 && mod != p-1) {
            mod = mulmod(mod, mod, p);
            temp <<= 1;
        }
        if(mod != p-1 && temp%2 == 0)   return false;
    }
    return true;
}

int main() {
    int t;
    s(t);
    w(t) {
        lli n, ans;
        sl(n);
        bool isPrime = false;
        while(Miller(n,2) == false) --n;
        printf("%lld\n", n);
    }
    return 0;
}