Problem: You are given a positive number x. Find the smallest positive integer number that has the sum of digits equal to x and all digits are distinct (unique).

Input

The first line contains a single positive integer t (1 ≤ t ≤ 50) — the number of test cases in the test. Then t test cases follow.

Each test case consists of a single integer number x (1 ≤ x ≤ 50).

Output

Output t answers to the test cases:

  * if a positive integer number with the sum of digits equal to x and all digits are different exists, print the smallest such number; 
  * otherwise print -1. 

Example

Input


4
1
5
15
50


Output


1
5
69
-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
// #define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<long long int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define per(i,b,a) for(ll i=(b);i>=(a);i--)
#define LLmin LLONG_MIN
#define LLmax LLONG_MAX

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

const ll mod = 1e9+7;
const ll N = 3*1e5+5;

ll gcd(ll, ll);
ll modPower(ll, ll, ll);
ll power(ll, ll);
ll modInverse(ll, ll);
// ll fact[N];


ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
ll modPower(ll x, ll y, ll m)
{
	if (y == 0)return 1;
	ll p = modPower(x, y / 2, m) % m;
	p = (p * p) % m;
	return (y % 2 == 0) ? p : (x * p) % m;
}
ll power(ll x, ll y)
{
	if (y == 0)return 1;
	ll p = power(x, y / 2);
	p = (p * p);
	return (y % 2 == 0) ? p : (x * p);
}
ll modInverse(ll a, ll m)
{
	return ((modPower(a, m - 2, m) + mod) % mod);
}

// Function to compute a/b under modlo m
ll modDivide(ll a, ll b, ll m)
{
    a = a % m;
    ll inv = modInverse(b, m);
    if (inv == -1)
       return 0;
    else
       return (inv * a) % m;
}

// ll nCr(ll n,ll r){
//     // just calculate factorial till N before using it.
//     ll ans=modDivide(fact[n],fact[r],mod);
//     ans=modDivide(ans,fact[n-r],mod);
//     return ans;
// }

bool myCompare(pii a,pii b){
     if(a.ff==b.ff) return a.ss<b.ss;
    return a.ff<b.ff;
}
/*------------------------------------CODE STARTS HERE------------------------------------------------*/
map<int,int> m;
int ans=-1;
bool trig=false;
string res;

vector<string> ans1;

int knap(int dig,int sum,int currDig,int currSum,string num){
    if(currDig==dig){
        if(currSum==sum && !trig){
            res=num;
            trig=true;
            return 1;
        }
        return 0;
    }
    if(trig) return 1;
    if(sum<currSum || currDig>9) return 0;
    
    rep(i,1,10){
        if(!m.count(i)){
            m[i]++;
            num+=to_string(i);
            int e=knap(dig,sum,currDig+1,currSum+i,num);
            m.erase(i);
            num=num.substr(0,currDig);
            if(e) return 1;
        }
    }
    
    
    return 0;
}

void solve() {
	int sum;
	cin>>sum;
	vector<int> as={1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,189,289,389,489,589,689,789,1789,2789,3789,4789,5789,6789,16789,26789,36789,46789,56789,156789,256789,356789,456789,1456789,2456789,3456789,13456789,23456789,123456789,-1,-1,-1,-1,-1,-1,-1};
	
	cout<<as[sum-1]<<"\n"; return;
	
// 	res=""; ans=-1; trig=false;
// 	int dig=-1;
// 	rep(i,1,6){
// 	    if(9*i>=sum){
// 	        dig=i; break;
// 	    }
// 	}
    
//     rep(i,dig,10){
//         int ans=knap(i,sum,0,0,"");
//         if(res!=""){
//             // cout<<res<<"\n";
//             ans1.pb(res);
//              return ;
//         }
//     }
	
// 	cout<<-1<<"\n";
//     ans1[sum]=-1;
    return;
}


int main() {
	fastIO;
	ll t = 1;
	cin >> t;
	rep(i, 0, t){
	   // cout<<"Case #"<<i+1<<": ";
	    solve();
	}
// 	for(auto i:ans1) cout<<i<<",";
	

	return 0;
} 


//