#include <cstdio>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stdint.h>
using namespace std;
typedef uint32_t Integer;
typedef uint64_t LongInteger;
const Integer maxn = 100000;
vector<Integer> primes;
bool nisprime[maxn+1];
void gen_primes(int n)
{
Integer nroot = Integer(sqrt(double(n)))+1;
primes.push_back(2);
nisprime[2] = true;
vector<Integer> s;
for(Integer i=3;i<n;i+=2){
s.push_back(i);
}
Integer m =3, i=0, j;
while(m<=nroot){
if(s[i]){
j = (m*m-3)/2;
s[j] =0;
while(j<s.size()){
s[j]=0;
j+=m;
}
}
i++;
m=2*i+3;
}
for(i=0;i<s.size();i++){
if(s[i]){
primes.push_back(s[i]);
nisprime[s[i]] = true;
}
}
}
Integer mod_mul(LongInteger a, Integer b, Integer n)
{
LongInteger res = 0;
while(b) {
// printf("in mod_mul, a=%llu, b=%u, n=%u\n", a, b, n);
if(b&1){
res += a;
while(res>=n){
res-=n;
}
}
a <<= 1;
b >>= 1;
// printf("in mod_mul, a=%llu, b=%u, n=%u\n", a, b, n);
while(a>=n){
a-=n;
}
}
return res;
}
Integer mod_exp(Integer a, Integer b, Integer n)
{
Integer res = 1;
while(b) {
if(b&1) res = mod_mul(res, a, n);
a = mod_mul(a, a, n);
//printf("a=%u,b=%u, res=%u\n", a, b, res );
b >>= 1;
}
return res;
}
Integer gcd(Integer a, Integer b)
{
if(a%b==0){
return b;
}
return gcd(b, a%b);
}
bool witness(Integer aa, Integer n) /*是以aa为底的伪质数返回0,是合数返回1*/
{
int t = 0;
Integer m = n-1;
while ((m % 2) == 0){ /*n = m * 2^t; */
m >>= 1;
++ t;
}
Integer x = mod_exp(aa, m, n), y;
//printf("aa=%u, m=%u\n", aa, m);
while (t --){
y = mod_mul(x, x, n);
//printf("x=%u,y=%u\n",x,y);
if (y == 1 && x != 1 && x != n-1) return 1;
x = y;
}
return (y != 1);
}
// int base[]={2,3,5,7,11,13,17};
int base[]={2,7,61};
bool deterministic_miller_rabin(Integer n)
{
if(n==2 || n==7 || n==61){return true;}
if((n&1)==0 || n==1){return false;}
for(int i=0;i<3;i++){
Integer a = base[i];
// if(a==n){return true;}
if(witness(a, n)){
//printf("witness a =%u\n", a);
return false;
}
}
return true;
}
bool isprime(Integer n)
{
if(n<=maxn){
if(nisprime[n]){
return true;
}
else{
return false;
}
}
else{
// if(miller_rabin_test(n)){
if(deterministic_miller_rabin(n)){
return true;
}
else{
return false;
}
}
}
Integer get_nearest_prime_less(Integer n)
{
if(n==2){return 0;}
if(n==3){return 2;}
if(n==4 || n==5){return 3;}
if(n==6||n==7){return 5;}
Integer t = n;
Integer nn=6*(t/6);
if(t-nn<=1){
t=nn-1;
if(isprime(t)){
return t;
}
t-=4;
}
else{
t=nn+1;
}
while(t>2){
if(isprime(t)){
return t;
}
t-=2;
if(isprime(t)){
return t;
}
t-=4;
}
return 0;
}
void test(){
clock_t t;
srand((unsigned)time(NULL));
unsigned p=4000000200u;
// printf("%u:%u\n", p, get_nearest_prime_less_2(p));
// printf("%d\n",isprime(p));
t = clock();
for(unsigned i=1; i<=10000; i++){
// unsigned n = rand()%(4294967295u-1234567890u)+1234567890u;
unsigned n = rand()%4294967295u;
// unsigned n = rand()%10000000u;
p = get_nearest_prime_less(n);
// printf("%u:%u\n", i, p);
}
t=clock()-t;
printf ("with miller:\nIt took me %ld clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC);
}
void solve()
{
int t;
unsigned n;
scanf("%d", &t);
while(t--){
scanf("%u", &n);
if(n>4294967291u){
printf("4294967291\n");
continue;
}
else{
printf("%u\n", get_nearest_prime_less(n));
}
}
}
void unittest(){
for(int i=0; i<100; i++){
test();
}
}
int main()
{
gen_primes(maxn);
solve();
// unittest();
// printf("%d\n",deterministic_miller_rabin(4000000187u));
return 0;
}
