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: AAYUESH BARUI #####
	## College: LNMIIT ###########
	##############################


*/

#include <bits/stdc++.h>
//========================================================================================================//
//========================================================================================================//
using namespace std;
//========================================================================================================//
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll > pll;
typedef vector<pll > vpll;
typedef vector<ll> vll;
//========================================================================================================//
#define rep(i,a,b) for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>=b;i--)
//========================================================================================================//
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define popb  pop_back
#define mem(a,b) memset(a,b,sizeof(a))
#define sz size()
#define MOD 1000000007

void boost()
{
        ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);
}
//cout<<"Case #"<<k<<": "<<ans<<endl;
ll power(ll a,ll b,ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}



int main() {
    boost();
    int test=1,i,j,k=1;
    cin>>test;
    while(test--) {
        int n;
        cin>>n;
        if(n>45)
            cout<<-1<<endl;
        else {
            int cu=0,v=10;

            while(cu<n) {
                v--;
                cu+=v;
            }
            //cout<<cu<<" "<<v<<endl;
            int d=cu-n;
            if(d==0) {
                for(int i=v;i<=9;i++)
                    cout<<i;
                cout<<endl;
                continue;
            }
            if(v!=d)
            {
                cout<<v-d;
                v++;
                for(int i=v;i<=9;i++)
                    cout<<i;
                cout<<endl;
            }
            else
            {
                for(int i=v;i<=9;i++)
                    cout<<i;
                cout<<endl;
            }
        }
    }
}