#include <iostream>
#include "stdlib.h"
#include "math.h"
using namespace std;

int main()
{
    int kol;
    int a[20];
    cin>>kol;
    for(int i=0; i<kol; i++)
    {
        cin>> a[i];

    }
    for(int i=0; i<kol; i++)
    {
    int p=0;
    int sum=0;
    int c=1;
    while(sum!=c)
    {
         p++;
        sum=0;
        c=0;
    int prov=a[i]+p;
        int l=prov;
        bool x=false;
        for(int j=3; j<=sqrt(prov); j++)
        {
            if(prov%j==0)
                x=true;
       }
        if(x==true)
        {
        for (int j=1; j<=l; j++)
        {
            if(prov>j)
            {
            if(prov%j==0 && j!=l && j!=1)
            {

                prov=prov/j;
            if(j>10)
            {
                int sumj=0;
                int h=j;
                while (h!=0)
                {
                    sumj+=h%10;
                    h=h/10;
                }
                sum=sum+sumj;
            }
            else
            {
            sum=j+sum;
            }
            j=j-1;

            }
            }
            }

             while (l!=0)
                {
                    c+=l%10;
                    l=l/10;
                }

        }
            else
                sum=-1;
        }
        cout<<a[i]+p;
    }

    return 0;
}
