//bsetbstebtbsetbsetbset
#include<bits/stdc++.h>

using namespace std;

int n,a;
int l = 1000005;
int prime[1000005], z[1000005];

void dan() {
    for (int i = 1;i <= l;i++)
        {prime[i] = 1;}

    prime[1] = 0;
    for (int i = 2;i <= l;i++) {
        if (prime[i] == 1) {
            for (int j = i+i;j <= l;j += i) {prime[j] = 0;}
        }
    }
    for (int i = 2;i <= l;i++) {
        if (prime[i] == 1) {z[i] = i;} else {z[i] = z[i-1];}
    }
}

int main() {
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    freopen("CLOPRIME.inp","r",stdin);
    freopen("CLOPRIME.out","w",stdout);

    cin>>n;
    dan();
    for (int i = 1;i <= n;i++) {
        cin>>a;
        cout<<z[a]<<endl;
    }
}