#include <fstream>
#include <cstring>
#include <iostream>
#define DIM 100000
using namespace std;

ifstream fin("superp.in");
ofstream fout("superp.out");
int T,j,n,sol,a[DIM],maxim,p,u,mask[DIM];
char s[20];
char v[DIM];
void ciur(){
    int i,j;
    v[1]=v[0]=1;
    for(i=2;i<=DIM;i++)
        if(!v[i])
        for(j=i+i;j<=DIM;j+=i)
            v[j]=1;
}
int main(){
    fin>>T;
    ciur();
    while(T--){
        fin>>s;
        n=0;
        memset(mask,0,sizeof(mask));
        maxim=0;
        for(j=0;s[j]!=0;j++){
            a[++n]=s[j]-'0';
            mask[n]=(1<<n-1);
            if(a[n]>maxim)
                maxim=a[n];
        }
        p=1;u=n;
        while(p<=u){
            for(j=1;j<=n;j++)
                if(!v[a[p]] && !v[a[p]*10+a[j]] && (mask[p]&mask[j])==0){
                    a[++u]=a[p]*10+a[j];
                    if(a[u]>maxim)
                        maxim=a[u];
                    mask[u]=(mask[p]+mask[j]);
            }
            p++;
        }
        fout<<maxim<<'\n';
    }
    fin.close();fout.close();
    return 0;
}