#include<stdio.h>
#include<math.h>
#define ERROR 0.00000001


int main()
{
    int prime[100005] = { 1, 1, 0 };
    int i, j;
    for( i = 2 ; i <= 100000 ; i++ )
        if( !prime[i] )
            for( j = i+i ; j <= 100000 ; j+=i )
                prime[j] = 1;

    int testcase;
    while( scanf( "%d", &testcase ) != EOF )
    {
        for( i = 1 ; i <= testcase ; i++ )
        {
            int n;
            scanf( "%d", &n );

            for( j = n+1 ; ; j++ )
            {
                int sum_left = 0, sum_right = 0;
                int temp = j;
                int sqrt_temp = (int)( sqrt((double)temp) + ERROR );
                int k;
                while( temp )
                {
                    sum_left += temp % 10;
                    temp /= 10;
                }

                temp = j;
                for( k = 2 ; k <= sqrt_temp ; k++ )
                {

                    if( !prime[k] )
                    {
                        while( !( temp % k ) )
                        {
                            temp /= k;
                            int k_temp = k;
                            while( k_temp )
                            {
                                sum_right += k_temp % 10;
                                k_temp /= 10;
                            }
                        }
                    }
                }
                if( temp > 1 )
                {
                    if( temp == j )
                        continue;
                    while( temp )
                    {
                        sum_right += temp % 10;
                        temp /= 10;
                    }
                }
                if( sum_left == sum_right )
                {
                    printf( "%d\n", j );
                    break;
                }
            }
        }
    }

    return 0;
}