/* @JUDGE_ID:4461XX 10042 C */
/* A */
#include<stdio.h>
#include<string.h>
#define MAX 100000

char prime[MAX] ;
int primetable[MAX] , poi ;
void make_prime( void )
{	
	int i , j ;

	memset( prime , 1 , sizeof( prime ) ) ;
	for( i=2,poi=0 ; i<MAX ; i++ )
		if( prime[i] ){
			primetable[poi++] = i ;
			for( j=2 ; i*j<MAX ; j++ ) prime[i*j] = 0 ;
		}
}
int count( int num )
{
	int sum ;
	
	for( sum=0 ; num ; ){
		sum += num % 10 ;
		num /= 10 ;
	}

	return sum ;
}
int issmith( int num )
{
	int tmp_n1 , tmp_n2 , i , change ;

	if( num<MAX )
		if( prime[num] ) return 0 ;
	tmp_n1 = count( num ) ;
	for( i=0,tmp_n2=0,change=0 ; i<poi ; )
		if( !( num%primetable[i] ) ){
			change++ ;
			tmp_n2 += count( primetable[i] ) ;
			if( tmp_n2>tmp_n1 ) return 0 ;
			num /= primetable[i] ;
		}
		else i++ ;

	if( num>=MAX ) tmp_n2 += count( num ) ;

	if( tmp_n1==tmp_n2&&change ) return 1 ;
	else return 0 ;
}
int main( void )
{
	int casetime , n , i ;

/*	freopen( "out" , "w" , stdout ) ;*/
	make_prime() ;
	scanf( "%d" , &casetime ) ;

	for( ; casetime ; casetime-- ){
		scanf( "%d" , &n ) ;

		for( i=n+1 ; ; i++ )
			if( issmith( i ) ){
				printf( "%d\n" , i ) ;
				break ;
			}
	}

	return 0 ;
}
/* @END_OF_SOURCE_CODE */