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;
 typedef long long int ll;




 int main()
 {
     ll p,n,m;
     cin>>p;
     while(p--)
     {
        // for(n=0;n<=50;n++){
         ll a,b;
         cin>>n;
        // cout<<n<<" = ";
         if(n>45) cout<<"-1\n";
         else
         {
             if(n<10) cout<<n<<"\n";
             else if( n>=10 && n<18)
             {
                 for(ll i=1;i<9;i++)
                 {
                     a=i;
                     b=n-i;
                     if(b<10) break;
                 }
                 cout<<a<<b<<"\n";
             }

            else if(n>=18  && n<=24)
             {
                 b=n-17;
                 cout<< b<<89<<"\n";
             }
           else  if(n>=25&& n<31)
             {
                 b=n-24;
                 cout<< b<<789<<"\n";
             }
            else if(n>=31&& n<36)
             {
                 b=n-30;
                 cout<< b<<6789<<"\n";
             }
            else if(n>=36&& n<40)
             {
                 b=n-35;
                 cout<< b<<56789<<"\n";
             }
            else if(n>=40&& n<43)
             {
                 b=n-39;
                 cout<< b<<456789<<"\n";
             }
            else if(n>=43&& n<45)
             {
                 b=n-42;
                 cout<< b<< 3456789<<"\n";
             }
             else if(n==45)
             {
                 cout<<123456789<<"\n";
             }
         }
        // }

     }
return  0;
 }