#include <cstdio>

int pros (int n) {
    int i = 2;
    int k = 1;

    while(i < n / 2) {
        if (n % i == 0) {
            k = 0;
            break;
        }
        else
            ++i;
    }
    return k;
}

int sum (int n) {

    int j = 0;

    while(n != 0) {
        j = j + (n % 10);
        n = n / 10;
    }
    return j;
}

int dub (int n) {

    int mas[35];
    int i = 2;
    int j = 0;

    while(n != 1) {
        if (n % i == 0) {
            mas[j] = i;
            n = n / i;
            ++j;
        }
        else
            ++i;
    }
    int k = 0;
    int res = 0;

    while(k < j) {
        res = res + sum(mas[k]);
        ++k;
    }
    return res;
}

int res (int n) {
    ++n;
    int i = 1;

    while(i != 0) {
        if (pros(n) == 1)
            ++n;
        else {
            if(dub(n) == sum(n))
                i = 0;
            else
                ++n;
        }
    }
    return n;
}


int main () {

    int n;
    scanf("%d", &n);

    int i = 0;
    while(i < n) {
        int k;
        scanf("%d", &k);
        printf("%d ", res(k));
        ++i;
    }
    return 0;
}




