10042

#include <iostream>

#include <string>
#include <vector>
#include <string.h>

using namespace std;

int prime[1000001];
vector <long long> vb;

long long sumof(long long a)
{
long long l=0;
while(a)
{
l+=a%10;
a/=10;
}
return l;
}

int isPrime(long long n)
{
if(n<1000001)
{
if(prime[n]==0)
return 1;
else
return 0;
}
for(int i=2;i*i<=n;i++)
if(n%i==0)
return 0;

return 1;
}
int factorsum(long long n)
{
if(n<1000001)
{
if(prime[n]==0)
return 1;
}

long long tmp=0;
long long org=n;
while(n)
{
int f=0;
for(int i=0;i<vb.size();i++)
{
if(vb[i]>n)
{
f=0;
break;
}
if(n%vb[i]==0)
{
tmp+=sumof(vb[i]);
n/=vb[i];
f=1;
break;
}
}
if(f==0)
{
if(isPrime(n)==1 && n!=org)
tmp+=sumof(n);
break;
}
}
//cout<<tmp<<" ds\n";
if(tmp==0)
return 1;
if(tmp==sumof(org))
return 0;

return 1;
}

int main()
{
prime[0]=1;
prime[1]=1;

for(int i=4;i<1000001;i+=2)
{
prime[i]=1;
}

for(int i=3;i*i<1000001;i+=2)
{
if(prime[i]==0)
{
for(int j=i+i;j<1000001;j+=i)
prime[j]=1;
}
}
//vb.clear();
vb.push_back(2);
for(int i=3;i<1000001;i+=2)
{
if(prime[i]==0)
vb.push_back(i);
}

int t;
long long n;
//cout<<vb[vb.size()-1]<<"\n";
//cout<<isPrime(1000000007)<<"\n";
//cout<<factorsum(1000000007)<<"\n";
//cout<<prime[45495]<<"\n";
//cout<<sumof(456502);
cin>>t;

while(t--)
{
cin>>n;
n++;
while(factorsum(n))
{
n++;
}
cout<<n<<"\n";
}

//getchar();
return 0;
}