#include<fstream>
#include<cmath>
using namespace std;
const int lim = 2000000;
int mx,vf,st[15]; long long N;
bool viz[15],zzz[15],a[10000002];

void back(int k){
     if(k>mx){ mx=k; }     
       if(k<=N)
         for(int i=vf;i>0;--i)
           if(k*10+st[i]<lim)
             if(!viz[i] && !a[k*10+st[i]]){
             viz[i]=1;
             back(k*10+st[i]);
             viz[i]=0;
             }                                                                
     }

int main(void){
    ifstream fin("superp.in");
    ofstream fout("superp.out");
    int T,i,j,xx,q,n; long long aux;
    n=lim; q=int(sqrt(n));
    for(i=2;i<=q;++i)
      if(!a[i])for(j=2;j<=n/i;++j)a[i*j]=1; 
    
    for(fin>>T;T;--T)
    {
     mx=vf=0; 
     fin>>N; aux=N; zzz[2]=zzz[3]=zzz[5]=zzz[7]=0;
     while(aux){ xx=aux%10; if(xx&1 || xx==2)st[++vf]=xx; aux/=10; }
     for(i=1;i<=vf;++i)
       if(!zzz[st[i]] && (st[i]==2 || st[i]==3 || st[i]==5 || st[i]==7)){
         zzz[st[i]]=1;
         viz[i]=1;
         back(st[i]);  
         viz[i]=0;   
         }           
     fout<<mx<<'\n';                
    }          
 return 0;   
}