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 ;

int main(){
   int test ;
     cin>>test;

    while(test--){

        int n ; 
        cin >> n  ;

 // for(i=1; i<=n;){
  //          if(k==0 || k==n)
  //            break;
  //          if(sum+1 <= i+1 && k>0){
  //              arr[i] = i ;
  //              sum += i;
  //               i++;
  //               k--;
  //               continue;
  //          }  
  //          if(sum >i){
  //            arr[i] = -i ; 
  //            sum -= i;
  //            i++;
  //             if(sum > 0 )
  //              k--;
  //              continue;
  //          }

  //          if(sum +1 > i+1 && k==1){
  //            arr[i] = -i ;
  //            i++;
  //             if(sum - i >0)
  //              break;
  //              else{
  //                sum -= i;
  //                 continue;
  //              }
  //          }
  //          if(sum+1 > i+1 && k<1){
  //             arr[i] = i; 
  //             if(sum > 0)
  //              k-- ;
  //              sum += i ;
  //               i++;
  //          }
  //     }
   
  //   if(k==n){
  //      REP(i,n)
  //        arr[i] = i ;
  //   }
  //    else if(i<=n){
  //      for(i<=n ; i++;)
  //       arr[i]-=i ;
  //    }


      if(n<10 )
        cout << n << endl; 

      else if (n>=10 && n<=17)
         cout <<n-9<<"9" << "\n";



      else if(n>=17 && n<=24)
        cout <<n-17<<"89" << endl;




         else if(n>24 && n<=30)
        cout <<n-24<< "789" << "\n";




        else if(n>30 && n<=35)
        cout <<n-30<<"6789" << endl;


        else if(n>35 && n<=39)
       cout <<n-35<<"56789" <<"\n";



       else if(n>39 && n<=42)
       cout <<n-39<<"456789" << "\n";  



        else if(n>42 && n<=44)
        cout <<n-42<<"3456789" << endl;  



      else if(n==45)
        cout <<"123456789" << "\n";  


       else{
         cout << "-1\n";
       }
      
    }
}