UVa 993

/*Basic info
Problem : UVa 993
Date : 13-01-19
Author : Shesher
*/

#include<bits/stdc++.h>

using namespace std;

///Template
#define in1()    freopen("C:\\Users\\SHESHER\\Rest\\Desktop\\MY COMPUTER\\Code\\Template\\input.txt", "r", stdin);
#define out1()   freopen("C:\\Users\\SHESHER\\Rest\\Desktop\\MY COMPUTER\\Code\\Template\\output.txt", "w", stdout);


//Data types
#define lo      long
#define ll      long long
#define llu     unsigned long long

//loop
#define f1(i,x,y)   for(int i=x;i<=y;i++)

//Constants
#define MAX     100007
#define MOD     10000007
#define PI      acos(-1.0)

//STL
#define vout(v)    for(int i=0;i<v.size();i++){cout<<v[i]; if(i==v.size()-1) cout<<endl; else cout<<" ";}

//Scan
#define sc(x)    scanf("%d", &x)
#define scl(x)   scanf("%lld", &x)

//Print
#define pa(a,i,n)  for(int i=0;i<n;i++){ cout<<a[i]; if(i==n-1) cout<<endl; else cout<<" ";}

vector<int> v;
ll mn;
bool f=0;
void div(ll n)
{
    if(n<10){
        v.push_back(n);
        ll num=0;
        for(int i=0;i<v.size();i++){
            num*=10;
            num+=v[i];
        }
        if(!f){
            mn=num;
            f=1;
        }
        else{
            if(num<mn) mn=num;
        }
        v.pop_back();
        return;
    }


    for(int i=2;i<=9;i++){
        if(i>sqrt(n)) break;
        if(n%i==0){
            v.push_back(i);
            div(n/i);
            v.pop_back();
        }
        // else return;
    }
}

int main()
{
    in1();
    out1();
    int n;
    cin>>n;
    while(n--){
        ll x;
        cin>>x;

        v.clear();
        f=0;
        mn=-1;
        div(x);

        cout<<mn<<endl;
    }
}