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:
//author-micheal corleone
//the godfather
#include <bits/stdc++.h>
#include <set> 
#include<algorithm>
#include <set> 
#include<algorithm>
#define ll long long int
#define in(n) scanf("%lld",&n)
#define in2(a,b) scanf("%lld %lld",&a,&b)
#define out(n) printf("%lld\n",n)
#define inf 999999999999999999
#define endl "\n"
#define precise(x) fixed << setprecision(x) 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
const int mod =1000000007;
#define f(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
 
using namespace std;

bool sortcol( const vector<int>& v1, 
               const vector<int>& v2 ) { 
 return v1[1] < v2[1]; 
}
 ll mod_pow(int a,int b,int M = mod)
{
    int res = 1;
    
    while(b)
    {
        if(b&1) res=(res*a)%M;
        a=(a*a)%M;
        b>>=1;
    }
    
    return res;
}
 //ll power(ll x, ll y) 
//{ 
  //  ll temp; 
    //if( y == 0) 
     //   return 1; 
    //temp = power(x, y/2); 
    //temp=temp%MOD;
    //if (y%2 == 0) 
     //   return (temp%MOD)*(temp%MOD); 
    //else
      //  return (x%MOD)*(temp%MOD)*(temp%MOD); 
//} 
 
 
ll ncr(ll n,ll r){if(n==1 || r==0)return 1;if(r>n/2)r=n-r;
	ll ans=1;for(ll i=1;i<=r;i++){ans=((ans * n )/i);n--;}return ans;
}
ll ncrsum(ll n,ll r, ll mod){
    if(n==1 || r==0)return 1;
  //  ll ans=1,sum=1;for(ll i=1;i<=r;i++){ans=((((ans * n)%MOD )*modinv(i,MOD))%mod);n--;sum+=ans;sum%=mod;}return sum;
}
 //diamond[2000005],ans[1000006];
 const int maxn=3e5+100;
 ll maximum=4000000;
 
 vector<ll> primes;
 vector<int>v[maxn];
ll dis[maxn]={0};
ll vis[maxn]={0};

 
void SieveOfEratosthenes() 
{ 
   
    vector<ll> prime(maximum+1,1); 
   // memset(prime, 1, sizeof(prime)); 
  
    for (ll p=2; p*p<=maximum; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == 1) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (ll i=p*p; i<=maximum; i += p) 
                prime[i] = 0; 
        } 
    } 
  
    
    for (ll p=2; p<=maximum; p++) 
    {
    	if (prime[p])
		{
			primes.pb(p); 
		 }     
	}
       
} 


 
 
int main()
{
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
     ll ta;
   cin>>ta;
    //SieveOfEratosthenes();
   // ta=1;	
     for(ll testcase=0;testcase<ta;testcase++)
    {
        ll i1,i2,j,j1,a1,i31,i3,j2,i5,i4,i6,i7,i,m,t,n,k;
        ll x,y,z;
        ll total=0,cnt=0;
        ll flag=0,flag1=0;
        y=0;
        ll res,res1,ans,res2,sum,curr;
        ans=0,cnt=0;
        res1=0,res=0,sum=0;
        ll required,days,h,w;
        ll s1=0,s2;
         ll k1,k2,k3,k4,p;
        k1=0,k2=0,k3=0,k4=0;
        //for(it=mp.begin();it!=mp.end(),it++)
        //{
        //	for(int i=0;i<it->second.size();i++) cout<<it->second[i]<<" ";
		//}
		  cin>>x;
          if(x>45)
          {
          	  cout<<-1<<endl;
          	  continue;
		  }
              vector<int> answer;
         for(int i = 9; i >= 1; --i) {
        if (x <= i) break;
        answer.push_back(i);
        x -= i;
        }
           answer.push_back(x);
          reverse(answer.begin(),answer.end());
          
          f(i,0,answer.size()) cout<<answer[i];
          
          cout<<endl;
          
       
	}
	   
	
    
}