#include<iostream>
#include<math.h>

using namespace std;

int sumNumbers(long n){
    int sum = 0;
    while (n > 0){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
int primeSum(long n){
    int sum = 0;
    bool prime = true;
    while(n % 2 == 0){
        n /= 2;
        sum += 2;
        prime = false;
    }
    for(int i = 3; i < sqrt(n)+1;){
        if(n % i == 0){
            n /= i;
            sum += sumNumbers(i);
            prime = false;

        }else{
            i += 2;
        }
    }
    if(!prime){
         sum+= sumNumbers(n);
    }
    return  sum;
}

int main(){
    int  n;
    cin >> n;
    int *numbers = new int[n];
    for(int i  = 0; i < n; i++){
        cin >> numbers[i];
    }
   for(int i = 0; i < n;i++){
        long j = numbers[i];
        while(sumNumbers(j) != primeSum(j)){
            j++;
        }
        cout << j <<" ";
   }
    return 0;
}
