#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("superp.in");
ofstream fout("superp.out");

int n, x[14], fr[10];
long long p, maxim, nr;
const int val[] = {2, 3, 5, 7, 0, 1, 0, 9};

bool Prim(int n)
{

    p = 0;
    if(n == 0) return 1;

    for(int i=1; i<=n; i++)
        p = p * 10 + x[i];

    if(p == 2) return 1;
    if(p % 2 == 0) return 0;
    else
        for(int i=3; i*i<=p ; i += 2)
            if(p % i == 0) return 0;
    return 1;
}

void Back(int k)
{
    if(!Prim(k-1));
    else
    {
        if(maxim < p) maxim = p;

        if(k == 1){
            for(int j=0; j<4; j++)
                if(fr[j])
                {
                    fr[j]--;
                    x[k] = val[j];
                    Back(k+1);
                    fr[j]++;
                }
        }
        else
            for(int j=1; j<8; j+=2)
                if(fr[j])
                {
                    fr[j]--;
                    x[k] = val[j];
                    Back(k+1);
                    fr[j]++;
                }
    }
}

void Citire()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
           fin>>nr;
           maxim = 0;
           for(int j=0; j<=9; j++)
                fr[j] = 0;

           while(nr)
           {
               int u = nr%10;

               if(u == 2) fr[0]++;
               else if(u == 3) fr[1]++;
               else if(u == 5) fr[2]++;
               else if(u == 7) fr[3]++;
               else if(u == 1) fr[5]++;
               else if(u == 9) fr[7]++;
               nr /= 10;
           }

           Back(1);

           fout<<maxim<<'\n';

    }
}

int main()
{
    Citire();


    return 0;
}