#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(void) {
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*/