#include<set>
#include<map>
#include<queue>
#include<ctime>
#include<array>
#include<cmath>
#include<string>
#include<bitset>
#include<vector>
#include<random>
#include<chrono>
#include<cstring>
#include<cassert>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include <unordered_set>
#include <unordered_map>

// define some stuffs
#define inf 0x3f
#define EPS 1.0e-4
#define maxD 10000
#define BUF_SZ 1 << 15
#define COSO 100000000
#define PI 3.1415926535897932384626433832795

#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<pii, int>
#define sz(x) (int)(x).size()
#define all(x)  (x).begin(), (x).end()

#define ll long long
#define ll long long
#define ld long double
#define ull unsigned long long

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front

#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define ALL(v) (v).begin(),(v).end()
#define __builtin_popcount __builtin_popcountll

using namespace std;

// Set up some constants
const int sll = 20;
const int sz1 = 1e5 + 15;
const int sz2 = 1e6 + 15;
const int sz3 = 1e7 + 15;
const int MOD1 = 1e7 + 5;
const int MOD2 = 1e9 + 5;
const int d4i[4] = {-1, 0, 1, 0};
const int d4j[4] = {0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1};
const int d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

// some necessary functions
inline namespace Input {
int pos, len;
char buf[BUF_SZ];

char next_char() {
 if (pos == len) {
  pos = 0;
  len = (int)fread(buf, 1, BUF_SZ, stdin);
  if (!len) {
   return EOF;
  }
 }
 return buf[pos++];
}

int read_int() {
 int x;
 char ch;
 int sgn = 1;
 while (!isdigit(ch = next_char())) {
  if (ch == '-') {
   sgn *= -1;
  }
 }
 x = ch - '0';
 while (isdigit(ch = next_char())) {
  x = x * 10 + (ch - '0');
 }
 return x * sgn;
}
}

inline namespace Output {
char buf[BUF_SZ];
int pos;

void flush_out() {
 fwrite(buf, 1, pos, stdout);
 pos = 0;
}

void write_char(char c) {
 if (pos == BUF_SZ) {
  flush_out();
 }
 buf[pos++] = c;
}

void write_int(int x) {
 static char num_buf[100];
 if (x < 0) {
  write_char('-');
  x *= -1;
 }
 int len = 0;
 for (; x >= 10; x /= 10) {
  num_buf[len++] = (char)('0' + (x % 10));
 }
 write_char((char)('0' + x));
 while (len) {
  write_char(num_buf[--len]);
 }
 write_char('\n');
}

void init_output() { assert(atexit(flush_out) == 0); }
}

int read() {
 int s = 0, f = 1; char ch = getchar();
 for(; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-')  f = 1;
 for(; '0' <= ch && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0';
 return s * f;
}

void write(int x) {
    if (x >= 10)
        write(x / 10);
    putchar (x % 10 + '0');
}

void BoostCompile(void) {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL); cout.tie(NULL);
}

void SetUpFile&#40;void&#41; {
 freopen("NAME.inp", "r", stdin);
 freopen("NAME.out", "w", stdout);
}

/* Author : Trần Vũ Hải Đăng */
const int N = 1e6 + 15;

int n, x;
bool check[N];
vector <int> k;

void sieve() {
    memset(check, true, sizeof(check));
    check[1] = false;
    for(int i = 2; i * i <= N; ++i) {
        if (check[i] == true) {
            for(int j = i * i; j <= N; j += i) {
                check[j] = false;
            }
        }
    }
}

void Solution(void) {
    sieve();
    cin >> n;

    for(int i = 1; i <= N; ++i) {
        if(check[i]) {
            k.push_back(i);
        }
    }

    for(int i = 1; i <= n; ++i) {
        cin >> x;
        int pos = upper_bound(k.begin(), k.end(), x) - k.begin();
        cout << k[pos - 1] << '\n';
    }
}

signed main (void) {
 BoostCompile();
 freopen("cloprime.inp", "r", stdin);
 freopen("cloprime.out", "w", stdout);
 Solution();
 return 0;
}

/* That's all about my code*/