#include <bits/stdc++.h>

using namespace std;
long long M(long long a)
{
    for (long long i=2; i*i<=a; i++)
        if (a%i==0) return i;
    return a;
}
long long S(long long a)
{
    long long res=0;
    while (a>0)
    {
        res=res+a%10;
        a=a/10;
    }
    return res;
}
bool IsSmit(long long a)
{
    if (M(a)==a) return false;
    long long res=0, t=S(a);
    while (M(a)>1)
    {
        res=res+S(M(a));
        a=a/M(a);
    }
    if (t==res) return true;
    return false;
}
int main()
{
    long long n;
    cin >> n;
    for (long long i=0; i<n; i++)
    {
        long long a;
        cin >> a;
        while (IsSmit(a)==false) a++;
        cout << a << " ";
    }
    return 0;
}
