#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll

const int N=5e4;

int lp[N+1];
vector<int> pr;

void precalc()
{
    lp[0]=lp[1]=1;
    for(int i=2;i<=N;i++)
    {
        //cout<<i<<"\n";
        if(lp[i]==0)
            lp[i]=i,pr.push_back(i);
        for(int j=0;j<pr.size();j++)
        {
            int p=pr[j];
            if(p*i>N||p>lp[i])
                break;
            lp[p*i]=p;
        }
    }
}

int sum(int x)
{
    int s=0;
    while(x)
        s+=x%10,x/=10;
    return s;
}

signed main()
{
    precalc();
    int n;
    cin>>n;
    while(n--)
    {
        int i;
        cin>>i;
        for(i++;i<=N*N;i++)
        {
            if(i<=N&&lp[i]==i)
                continue;
            int s1=sum(i);
            int s2=0;
            int t=i;
            if(i<=N)
                while(t>1)
                    s2+=sum(lp[t]),t/=lp[t];
            else
            {
                bool prime=true;
                for(int j=0;j<pr.size();j++)
                {
                    int p=pr[j];
                    if(p*p>t)
                        break;
                    while(p*p<=t&&t%p==0)
                        prime=false,s2+=sum(p),t/=p;
                }
                if(prime)
                    continue;
                if(t>1)
                    s2+=sum(t);
            }
            if(s1==s2)
            {
                cout<<i<<" ";
                break;
            }
        }
    }
}
