#include <bits/stdc++.h>
using namespace std;
ifstream fin("superp.in");
ofstream fout("superp.out");
int n,fr[10],i,j;
long long nr,sol,smax;
int prim(int x)
{
    int d=2;
    if(x<2) return 0;
    for(d=2;d*d<=x;d++)
        if(x%d==0) return 0;
    return 1;
}
void bkt(int k)
{
    for(int i=1;i<=9;i++)
    if(fr[i] && prim(sol*10+i))
    {
        sol=sol*10+i;
        smax=max(smax,sol);
        fr[i]--;
        bkt(k+1);
        sol=sol/10;
        fr[i]++;
    }
}
int main()
{
    fin>>n;

    for(i=1;i<=n;i++)
    {
        fin>>nr;
        sol=0;
        while(nr)
        {
            fr[nr%10]++;
            nr/=10;
        }
        smax=0;
        bkt(1);
        fout<<smax<<'\n';
        for(j=1;j<=9;j++) fr[j]=0;
    }
    return 0;
}