#include <iostream>
using namespace std;
bool pierwsza(int liczba)
{
if(liczba<=1)
{
return false;
}
else
{
for(int i=2;i*i<=liczba;i++)
{
if(liczba%i==0)
{
return false;
}
}
return true;
}
}
int main()
{
int t,liczba,licznik;
cin>>t;
for(int j=0;j<t;j++)
{
cin>>liczba;
if(pierwsza(liczba)==true)
cout<<liczba<<endl;
else
{
if(liczba%2==0)
{
liczba-=1;
if(pierwsza(liczba)==true)
{
cout<<liczba<<endl;
continue;
}
}
licznik=2;
while(licznik>-1)
{
if(pierwsza(liczba+licznik)==true)
{
if(pierwsza(liczba-licznik)==true)
cout<<liczba-licznik<<endl;
else
cout<<liczba+licznik<<endl;
break;
}
else if(pierwsza(liczba-licznik)==true)
{
cout<<liczba-licznik<<endl;
break;
}
else licznik+=2;
}
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKYm9vbCBwaWVyd3N6YShpbnQgbGljemJhKQp7CiAgICBpZihsaWN6YmE8PTEpCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGZvcihpbnQgaT0yO2kqaTw9bGljemJhO2krKykKICAgICAgICAgICAgewoKICAgICAgICAgICAgIGlmKGxpY3piYSVpPT0wKQogICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQp9CmludCBtYWluKCkKewogICAgaW50IHQsbGljemJhLGxpY3puaWs7CiAgICBjaW4+PnQ7CiAgICBmb3IoaW50IGo9MDtqPHQ7aisrKQogICAgewogICAgICAgIGNpbj4+bGljemJhOwogICAgICAgIGlmKHBpZXJ3c3phKGxpY3piYSk9PXRydWUpCiAgICAgICAgICAgIGNvdXQ8PGxpY3piYTw8ZW5kbDsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBpZihsaWN6YmElMj09MCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGljemJhLT0xOwogICAgICAgICAgICAgICAgaWYocGllcndzemEobGljemJhKT09dHJ1ZSkKICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgIGNvdXQ8PGxpY3piYTw8ZW5kbDsKICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGxpY3puaWs9MjsKICAgICAgICAgICAgd2hpbGUobGljem5paz4tMSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYocGllcndzemEobGljemJhK2xpY3puaWspPT10cnVlKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmKHBpZXJ3c3phKGxpY3piYS1saWN6bmlrKT09dHJ1ZSkKICAgICAgICAgICAgICAgICAgICAgICAgIGNvdXQ8PGxpY3piYS1saWN6bmlrPDxlbmRsOwoKICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgY291dDw8bGljemJhK2xpY3puaWs8PGVuZGw7CgogICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgIGVsc2UgIGlmKHBpZXJ3c3phKGxpY3piYS1saWN6bmlrKT09dHJ1ZSkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgY291dDw8bGljemJhLWxpY3puaWs8PGVuZGw7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgIGVsc2UgbGljem5pays9MjsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICB9CiAgICByZXR1cm4gMDsKfQo=