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:
/*
anshu shandilya
*/
/*
2300 codechef rating before 31 December 2020
*/
/*
2100 codeforces rating before 31 December 2020
*/




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

typedef long double LD;
typedef long long ll;
#define int ll
#define itn int
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define rev(v) v.begin(),v.end(),greater<int>()
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define ff first
#define ss second
#define pq(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define wt(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);
const int MAXN = 1000005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);

#ifdef int
const int INF=1e16;
#else
const int INF=1e9;
#endif

const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;

/**************************  finding a number is prime or not and smallest prime factor of any number  *******************************/
bool primes[100001];
int spf[100001];

void sieve()
{
	 primes[0]=primes[1]=false;
	 for(int i=1;i<=100000;i++)
	 {
	 	 spf[i]=i;
	 	 primes[i]=true;
	 }
	 spf[2]=2;
	 for(int i=4;i<=100000;i+=2)
	 {
	 	 spf[i]=2;
	 	 primes[i]=false;
	 }
	 for(int i=3;i*i<=100000;i+=2)
	 {
	 	 if(spf[i]==i)
	 	  {
	 	  	  for(int j=i*i;j<=100000;j+=i)
	 	  	  {
	 	  	  	 if(spf[j]==j)
	 	  	  	  spf[j]=i;
	 	  	  	 primes[j]=false;
			  }
		  }
	 }
	 return ;
}

/******************************************** code ends *******************************************************************/


/*********************************************  modulo exponentation *****************************************************/
int power(int n, int m,int p)
{
	 int res=1;
	 n=n%MOD;
	 while(m>0)
	 {
	 	 if(m&1)
	 	 {
	 	 	 res=((res)%p*(n)%p)%p;
	 	 	 m--;
		 }
		  n=((n)%p*(n)%p)%p;
		  m>>=1;
	 }
	 return res;
}

/************************************************  code ends *************************************************************/









/********************************* NcR MOD P in O(1) for queires type probs ******************************************/
int N=10000;
int factorialNumInverse [100001];
int naturalNumInverse[100001];
int fact[100001];

void InverseofNumber(ll p)
{
    naturalNumInverse[0] = naturalNumInverse[1] = 1;
    for (int i = 2; i <= N; i++)
        naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
void InverseofFactorial(ll p)
{
    factorialNumInverse[0] = factorialNumInverse[1] = 1;

    for (int i = 2; i <= N; i++)
        factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}

void factorial(ll p)
{
    fact[0] = 1;

    for (int i = 1; i <= N; i++) {
        fact[i] = (fact[i - 1] * i) % p;
    }
}

int Binomial(int N, int R, int p)
{
    int ans = ((fact[N] * factorialNumInverse[R])
              % p * factorialNumInverse[N - R])
             % p;
    return ans;
}

/********************************** CODE ENDS ******************************************************************************/


/*********************************** NcR MOD p using FERMAT'S THEOREM IN O(LOGY) ******************************************/


int modInverse(int n,int p)
{
    return power(n, p - 2, p);
}

int nCrModPFermat(int n,int r, int p)
{

    if (n < r)
        return 0;
    if (r == 0)
        return 1;

    int fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}


/**************************************** CODE ENDS ***********************************************************************/





void solvethetestcase();

signed main()
{
    FAST_IO
    //sieve();
    int t = 1;
    cin >> t;
    FOR(testcase,1,t+1){
       // printf("Case #%lld: ",testcase);
        solvethetestcase();
    }

}

int n,m,a,b,c,x,zero,p,t1,t2,t,q,cnt;






/*********************************************  REAL CODE STARTS **********************************************************/
void solvethetestcase(){
    cin>>x;
	set<int>st;
	string s="123456789";
	n=s.length();
	vi vec,ans;
	int sz=INT_MAX;
	string s1,res="";
	for(int i=0;i<pow(2,n);i++)
	{
		int sum=0;
		vec.clear();
		s1="";
		 for(int j=0;j<n;j++)
		 {
		 	  if(i&(1<<j))
		 	   {
		 	   	 sum+=s[j]-'0';
		 	   	 s1+=s[j];
			   }
		 }
		     if(sum==x)
			 {
			 
		 	 if(res=="")
		 	 res=s1;
		 	 else if(s1.compare(res))
		 	 res=s1;
		 	 
		     }
		 	 
		 
		 
	}
	if(res.length()>0)
	{
		cout<<res;
	}
	else
	cout<<-1;
	cout<<"\n";

	
}

/************************************************ CODE ENDS ***************************************************************/