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:
//Created by Hemant Raj
#include <bits/stdc++.h> 
#include <iomanip>
#include<algorithm>
#include<vector>
#include<string>
#include <unordered_map> 
#include<set>
using namespace std; 

typedef long long int ll; 
typedef vector<int> vi;
typedef vector<vector<int>> vvi; 
typedef pair<int, int> pi; 

#define max(a, b) (a < b ? b : a) 
#define min(a, b) ((a > b) ? b : a) 
#define mod 1e9 + 7 
#define INF 1000000000000000003 

#define lb                   lower_bound
#define ub                   upper_bound
#define mine                *min_element
#define maxe                *max_element
#define pb   push_back
#define POB pop_back 
#define MP make_pair 

#define F                    first
#define S                    second
#define ceil(x,a)             ((x + a - 1)/(a))
#define all(v)               v.begin(), v.end()
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
#define read_ar(ar, n,k)           for (int ele = k; ele < n+k; ele++)cin>>ar[ele];
#define print_ar(ar, n,k)          for (int ele = k; ele < n+k; ele++)cout<<ar[ele]<<" ";

bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) {return (a.second < b.second);}
//Prime_Seive
bool prime[1000000+1]; void seive(){ ll N=1e6+1; memset(prime,true,sizeof(prime)); prime[0]=false; prime[1]=false; for(ll i=2;i*i<=N;i++){ if(prime[i]){ for(ll j=i*i;j<=N;j+=i){ prime[j]=false;}}}}
// check whether the given number is pow of 2
bool isPowerOfTwo(int x) {return (x && !(x & (x - 1)));}
  bool is_prime(int n){
             if(n==1) return false;
            for(int i=2;i<=sqrt(n);i++){
                       if(n%i==0){
                            return false;      
                       }
            }
            return true;
  
}

// DFS
//ll ans=1;
/*
int const G=100005;
map<ll,int>lefts;
int ar[G];
ll pre[G];

int vst[G];
vector<int> edge[G];
*/
// ll ar[G];


 /*
int dfs(int sv,int temp){
     vst[sv]=1;
     temp=min(temp,ar[sv]);
     for(int i=0;i<edge[sv].size();i++){
        int x=edge[sv][i];
       if(!vst[x]){
      
        dfs(x,temp);
        
       }
     }
     return temp;
}
*/
/*
ll bfs(int sv){
  queue<int>pn;
  pn.push(sv);
  vst[sv]=1;
  ll temp=ar[sv];
  while(!pn.empty()){
    int x=pn.front();
     vst[x]=1;
    pn.pop();
    for(int i=0;i<edge[x].size();i++){
      if(!vst[edge[x][i]]){
      pn.push(edge[x][i]);
      temp=min(temp,ar[edge[x][i]]);
    }
    }
  }
  //cout<<temp<<" ";
  return temp;
}
*/




void hemant(){

   string s="";
   ll n,m,k;
   cin>>n;
   
   if(n>45){
         cout<<"-1"<<"\n";
         return ;
   }
   if(n>=1 && n<=9){
         cout<<n<<"\n";
         return;
   }
   if(n>=10 && n<18){
         cout<<n-9<<"9"<<"\n";
   }
   if(n>=18 && n<25){
         cout<<n-17<<"89"<<"\n";
   }
   if(n>=25 && n<31){
         cout<<n-24<<"789"<<"\n";
   }
   if(n>=31 && n<36){
      cout<<n-30<<"6789"<<"\n";
} 
if(n>=36 && n<40){
      cout<<n-35<<"56789"<<"\n";
}
if(n>=40 && n<43){
      cout<<n-39<<"456789"<<"\n";
}
if(n>=43 && n<45){
      cout<<n-42<<"3456789"<<"\n";
}
if(n==45){
      cout<<"123456789"<<"\n";
}
   
}

int main(){
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input_hemant.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output_hemant.txt", "w", stdout);
#endif
      
     fast_io;
      
     int t=1; 
    cin>>t;
     while(t--){
          hemant();
     }
     return 0;       
}