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

long long NumberSum (long long a) { //+
    long long res = 0;
    while (a > 10) {
        res += a%10;
        a /= 10;
    }

    return res + a;
}

bool IsPrime (long long a) { //+
    if (a <= 1) return false;
    for (int i = 2; i <= sqrt(a); ++i) {
        if (a % i == 0) return false;
    }

    return true;
}

long long NearestDiv (long long n) { //+
    for (int i = 2; i <= n/2; ++i) {
        if (n % i == 0)
            return i;
    }

    return -1;
}

bool IsSmith (long long n) {
    std::vector<long long> divs; int sizeArr = 0;
    long long n0 = n;

    while (!IsPrime(n)) {
        divs.push_back(NearestDiv(n)); ++sizeArr;
        n /= NearestDiv(n);
    }

    divs.push_back(n); ++sizeArr;

    long long sum0 = 0, sum = 0;
    for (int i = 0; i < sizeArr; ++i) {
        sum += NumberSum(divs[i]);
    }

    sum0 = NumberSum(n0);

    return (sum0 == sum);
}

long long NearestSmith (long long a) {
    ++a;

    while (!IsSmith(a) || IsPrime(a)) {
        ++a;
    }

    return a;
}

int main()
{
    std::vector <long long> numbers;
    long long N = 0; std::cin >> N; numbers.resize(N);
    for (int i = 0; i < N; ++i) std::cin >> numbers[i];

    for (int i = 0; i < N; ++i) {
        std::cout << NearestSmith(numbers[i]) << " ";
    }
    return 0;
}
