#include <iostream>
#include<vector>
using namespace std;
bool prime[100000];
vector<int> primes;
void primelist(){
for (int i=0;i<100000;i++){
prime[i]=true;
}
prime[0]=false;
prime[1]=false;
for (int i=2; i<100000; i++){
if (prime[i]){
if((long long)i*i<100000){
for(int m=i*i; m<100000; m+=i)
prime[m] = false;
}
primes.push_back(i);
}
}
}
int bit_sum(int num){
int sum=0;
while(num){
sum+=num%10;
num/=10;
}
return sum;
}
int prime_sum(int num){
int sum=0,i=0;
while(primes[i]<=num&&i<primes.size()){
while(num%primes[i]==0){
sum+=bit_sum(primes[i]);
num/=primes[i];
}
i++;
}
if(num!=1)
sum+=bit_sum(num);
return sum;
}
int isprime(int num){
int i=0;
while(i<primes.size()&&primes[i]<num){
if(num%primes[i]==0){
return 0;
}
i++;
}
return 1;
}
int findsmith(int number){
for (int i=number+1;i<1e-9;i++){
if(isprime(number)) continue;
if(prime_sum(i)==bit_sum(i)){
return i;
}
}
}
int main()
{
primelist();
int t,n;
cin>>t;
while(t--){
cin>>n;
cout<<findsmith(n)<<endl;
}
return 0;
}