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>
    // #include<ext/pb_ds/assoc_container.hpp>
    // #include<ext/pb_ds/tree_policy.hpp>
using namespace std;
        // using namespace __gnu_pbds;

typedef long long int lli;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<lli,lli> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii>vpii;
typedef std::vector<lli> vll;
typedef std::vector<pll> vpll;
typedef std::vector<bool> vbb;
typedef map<lli,lli>mll;
typedef set<lli> sll;
typedef multiset<lli> msll;
const lli MOD=0ll;
const lli INF=3e18;

    #define forr(i,p,n) for(i=p; i<n; i++)
    #define forn(i,p,n) for(i=p; i<=n; i++)
    #define forl(i,n,p) for(i=n; i>=p; i--)
    #define be(a) a.begin(),a.end()
    #define mp make_pair            
    #define eb emplace_back 
    #define pb push_back 
    #define F first
    #define S second
    #define all(a)     (a).begin(),(a).end()
    #define PI 3.14159265358979323846
    #define lb lower_bound
    #define ub upper_bound
    #define endl "\n"
    #define bpcl(x) __builtin_popcountll(x)
    #define deb(vari) cerr<<#vari<<" = "<<vari<<endl;
                // #define ordered_set tree<lli, null_type,less<lli>, rb_tree_tag,tree_order_statistics_node_update> 
lli power(lli base, lli exp) {lli res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}
lli bitc(lli n,lli x){return ((n>>x)&1);}
lli __gcd(lli a,lli b){return b==0?a:__gcd(b,a%b);}
lli fsub(lli a,lli b,lli p=MOD){return ((a%p)-(b%p)+p)%p;}
lli fmult(lli a,lli b, lli p=MOD) {return ((((a%p)*(b%p))%p)+p)%p;}
lli fadd(lli a, lli b, lli p=MOD) {return ((a%p + b%p)%p+p)%p;}
                                        // lli add(lli a,lli b,lli p=MOD){//if(a+b>=p){//return (a+b)-p;//  }//return a+b;// }
lli fpow(lli n, lli k, lli p = MOD) {lli r = 1; while(k > 0) {if (k & 1) r = r * n%p; n = n * n%p; k = k >> 1;} return r;}
lli inv(lli a, lli p = MOD) {return fpow(a, p - 2, p);}
lli fdiv(lli a,lli b,lli p=MOD){lli yinv=inv(b);lli ans=(a*yinv)%p;return ((ans)%p+p)%p;}
lli ceil(lli a,lli b){return ceil((ld)a/b);}

    template<typename T>istream &operator>>(istream &in, vector<T> &a) {for (auto &item : a) {in >> item;}return in;}template<typename T,typename U>ostream &operator<<(ostream &out, pair<T,U> &a) {cout<<a.F<<" "<<a.S;return out;}
    template<typename T,typename U>
istream &operator>>(istream &out, pair<T,U> &a) {cin>>a.F>>a.S;return out;}
    template<typename T,typename U>
ostream &operator<<(ostream &out, map<T,U> &a) {for (auto &item : a) {out << item << endl;}return out;}
    template<typename T>
ostream &operator<<(ostream &out, vector<T> &a) {for (auto &item : a) {out << item << " ";}return out;}
    template<typename T>
ostream &operator<<(ostream &out, vector<vector<T>> &a) {for (auto &item : a) {out << item << "\n";}return out;}
    template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
                          template<typename... Args>
	Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
	}
};
    template<typename T>
struct Vec<1, T> : public vector<T> {
	Vec(int n = 0, T val = T()) : vector<T>(n, val) {
	}
};
/*
Vec<5, int> dp;
dp.assign(n1, {n2, n3, n4, n5, default_value});
*/

                    // Vec<2,lli>mat(n,n,1);
    #define print(a) for(auto p:a) cout<<p<<endl; cout<<endl;
    #define read(a) for(auto &p:a)cin>>p>>endl;
std::vector<bool> is_prime;
std::vector<lli> primes;
void sieve(lli n){is_prime.resize(n+2,true);primes.clear();lli p;for(p=2;p*p<=n;p++){if(is_prime[p]){lli i;for(i=p*p;i<=n;i+=p){is_prime[i]=false;}}}is_prime[0]=is_prime[1]=false;lli i;for(i=2;i<=n;i++){if(is_prime[i]){primes.eb(i);}}}
mll prime_factors(lli n){  mll s;lli i;lli tc=0;while(n%2==0){tc++;n/=2;}if(tc>0){s[2]=tc;}for(i=3;i<=sqrt(n);i+=2){tc=0;while(n%i==0){tc++;n/=i;}if(tc>0){s[i]=tc;}}if(n>2){s[n]+=1;}return s;}
std::vector<lli> fact_vec;
void fact_fun(lli n){fact_vec.resize(n+10);lli i;fact_vec[0]=1;for(i=1;i<=n+2;i++){fact_vec[i]=(fact_vec[i-1]*i)%MOD;}}
vll p2;
void power_2(lli n,lli m=MOD){ lli i;p2.eb(1);forr(i,0,n){p2.eb(fmult(p2.back(),2));}}
lli ncr(lli n,lli r){if(r>n)return 0;return fdiv(fact_vec[n],fmult(fact_vec[r],fact_vec[n-r]));}
vll spf;void sieve2(lli MAXN) { MAXN+=10;spf.resize(MAXN,0);spf[1] = 1; for (lli i=2; i<MAXN; i++) spf[i] = i;     for (lli i=4; i<MAXN; i+=2) spf[i] = 2; for (lli i=3; i*i<MAXN; i++) {         if (spf[i] == i) { for (lli j=i*i; j<MAXN; j+=i) {if (spf[j]==j) spf[j] = i; }} } } 
const int mi[4]={-1, 0, 1, 0}, mj[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
mll getFactorization(lli x) 
{ 
	mll ret; 
	while (x != 1){ 
        // ret.eb(spf[x]); 
		ret[spf[x]]++;
		x = x / spf[x]; 
	} return ret; 
}


class Sol{    
public:        
	Sol(){      
		lli  i,j;          
	}         
};

int main(){    

	lli i,j;
            #ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);   
	freopen("output.txt",  "w", stdout);
            #endif

	ios::sync_with_stdio(false);    
	cin.tie(0);


	lli ti;
	ti=1;
        cin>>ti;       
	while(ti--){    
		lli n;
		cin>>n;
		vll ans;
		lli fans=INF;
		forr(i,0,(1ll<<9)){
			vll v;
			forr(j,0,9){
				if(bitc(i,j)){
					v.eb(j+1);
				}
			}

			if(accumulate(all(v),0ll)==n){
				sort(all(v));	
				lli cur=0;
				lli tp=1;
				lli k;
				forl(k,(lli)v.size()-1,0){
					cur+= tp*v[k];
					tp*=10;
				}
				fans=min(fans,cur);

			}
		}
		if(fans==INF){
			fans=-1;
		}
		cout<<fans<<endl;
	}
	return 0;

}