Untitled

#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;
}