#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

const int super_prim = 1000;
const long long lim_max = (long long)1000000 * 1000000;//adaug inca 7 zerouri si trec le long long
const int rad_lim_max = 1000000;
long long coada[super_prim], NR = 0;
long long cifre[super_prim][10];
//int cprime[] = {2, 3, 5, 7};
int cif[10];
int prime[2 * rad_lim_max + 10], nrprime = 0;

void ciur()
{
	bool e[2 * rad_lim_max + 10] = {0};
	for(int i = 2 ; i * i <= 2 * rad_lim_max ; i++)
		if(!e[i])
			for(int j = i * i ; j <= 2 * rad_lim_max ; j += i)
				e[j] = 1;
			
	for(int i = 2 ; i <= 2 * rad_lim_max ; i++)
		if(!e[i])
			prime[++nrprime] = i;
}

bool prim(long long x)
{
	for(int i = 1 ; prime[i] * prime[i] <= x ; i++)
		if(x % prime[i] == 0)
			return 0;
	return 1;
}

void face_coada()
{
	coada[++NR] = 2;cifre[NR][2]++;
	coada[++NR] = 3;cifre[NR][3]++;
	coada[++NR] = 5;cifre[NR][5]++;
	coada[++NR] = 7;cifre[NR][7]++;
	
	for(int i = 1 ; i <= NR ; i++)
		for(int k = 1 ; k <= 9 ; k++)
			if(coada[i] * 10 + k <= lim_max && prim(coada[i] * 10 + k))
			{
				coada[++NR] = coada[i] * 10 + k;
				for(int l = 1 ; l <= 9 ; l++)
					cifre[NR][l] = cifre[i][l];
				cifre[NR][k]++;
			}
}

void descompune(long long x)
{
	fill(cif + 1, cif + 10 , 0);
	while(x)
	{
		cif[x % 10]++;
		x /= 10;
	}
}

long long cauta()
{
	for(int i = NR ; i ; i--)
	{
		bool b = 1;
		for(int l = 1 ; l <= 9 ; l++)
			if(cifre[i][l] > cif[l])
			{
				b = 0;
				break;
			}
		if(b == 1)
			return coada[i];
	}
}

int main()
{
	freopen("superp.in", "r", stdin);
	freopen("superp.out", "w", stdout);
	ciur();
	face_coada();
	int T;
	long long	x;
	cin >> T;
	for(int i = 1 ; i <= T ; i++)
	{
		cin >> x;
		descompune(x);
		printf("%lld\n", cauta());
	}
	return 0;
}