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;
#define ld long double
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,n) for(ll i=0;i<n;i++)
#define fa(i,a,b) for(ll i=a;i<=b;i++)
#define fr(i,n) for(ll i=n-1;i>=0;i--)
#define fi first
#define se second
#define vll vector<ll>
#define mll map<ll,ll>
#define sll set<ll>
#define pll pair<ll,ll>
#define endl "\n"
#define all(a) a.begin(),a.end()
#define en cout<<endl;
#define deb(x) cout<<#x<<" "<<x<<" ";
#define csp(x) cout<<fixed<<setprecison(x)
#define setbits(x) __builtin_popcount(x)
#define an ll n;cin>>n;ll a[n];f(i,n)cin>>a[i];



int main()
{

ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);


#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif



   ll t;
   cin>>t;
   while(t--)
   {
     int x;
     cin>>x;
     if(x>45)cout<<-1;
     else
     {
        vector<ll>ans;
        fa(i,1,9)
        {
          
          map<ll,ll>m;
          ll temp=x;
          ll c=i;

          while(temp>0)
          {
            if(temp>=c)
            {   if(c>9)
                  break;
                temp-=c;
                m[c]++;
                c++;
            }
            else
            {
              if(temp<=9&&m.find(temp)==m.end())
                m[temp]++, temp-=temp;
              else break;
            }
          }
          
          if(temp==0)
          {
            ll s=0;
            for(auto x:m)
              s=s*10+x.fi;
            ans.pb(s);
            //cout<<s<<" "<<i<<endl;
          }


        }

        cout<<*min_element(all(ans));
        
     }

     en
   }
 

}