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:

// ░█████╗░██████╗░██╗░░██╗██╗███╗░░██╗░█████╗░███╗░░██╗██████╗░░█████╗░███╗░░██╗
// ██╔══██╗██╔══██╗██║░░██║██║████╗░██║██╔══██╗████╗░██║██╔══██╗██╔══██╗████╗░██║
// ███████║██████╦╝███████║██║██╔██╗██║███████║██╔██╗██║██║░░██║███████║██╔██╗██║
// ██╔══██║██╔══██╗██╔══██║██║██║╚████║██╔══██║██║╚████║██║░░██║██╔══██║██║╚████║
// ██║░░██║██████╦╝██║░░██║██║██║░╚███║██║░░██║██║░╚███║██████╔╝██║░░██║██║░╚███║
// ╚═╝░░╚═╝╚═════╝░╚═╝░░╚═╝╚═╝╚═╝░░╚══╝╚═╝░░╚═╝╚═╝░░╚══╝╚═════╝░╚═╝░░╚═╝╚═╝░░╚══╝
// ███████████████████████████████████████████████████████
// █▄─▄█─▄▄▄▄███─▄─▄─█─█─█▄─▄▄─███▄─▄─▀█▄─▄▄─█─▄▄▄▄█─▄─▄─█
// ██─██▄▄▄▄─█████─███─▄─██─▄█▀████─▄─▀██─▄█▀█▄▄▄▄─███─███
// ▀▄▄▄▀▄▄▄▄▄▀▀▀▀▄▄▄▀▀▄▀▄▀▄▄▄▄▄▀▀▀▄▄▄▄▀▀▄▄▄▄▄▀▄▄▄▄▄▀▀▄▄▄▀▀
// ╔══╗
// ╚╗╔╝
// ╔╝(¯`v´¯)
// ╚══`.¸.Coding
 
 
/*       *********
 *       *
 *   *   *   *
 *       *
 *****************
         *       *
     *   *   *   *
         *       *
 *********       */
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long int
#define ll long long int
#define fi(n) for(int i=0;i<n;i++)
#define fj(n) for(int j=0;j<n;j++)
#define W(x) int x;cin>>x;while(x--)
#define fr(n) for(int i=n-1;i>=0;i--)
#define mp make_pair
#define fo(i,a,n) for(int i=a;i<n;i++)
#define ps(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define vi vector<int>
#define deb(x) cout<<#x<<"="<<x<<endl;
#define all(a) (a).begin(),(a).end()
#define pii pair<int,int>
#define sortall(x) sort(all(x))
#define mk(arr,n,type)  type *arr=new type[n];
#define vpi vector<pair<int,int> >
#define setbits(x) __builtin_popcountll(x)
#define zerbits(x) __builtinctzll(x)
#define mod 1000000007
#define inf 1e18
#define sz(x) (int)x.size()
#define vs vector<string>
#define itr(a) for(auto it=a.begin();it!=a.end();it++)
#define f first
#define s second
#define INT_SIZE 32
int mpow(int exp, int base);
//I don't know what the funciton aeh() does but it speeds up my mess
void aeh()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
int32_t main()
{
	aeh();
	int t;cin>>t;
	while(t--)
	{
		int x;
		cin>>x;
		vi res;
		if(x<=45)
		{
			for(int i=9;i>0;i--)
			{
				if(x-i>=0)
				{
					res.pb(i);
					x-=i;
				}

			}
			for(int i=res.size()-1;i>=0;i--)
				cout<<res[i];
			cout<<endl;
		}		
		else
			cout<<-1<<endl;
	}
}

int mpow(int base, int exp)
{
	base %= mod;
	int result = 1;
	while (exp > 0)
	{
		if (exp & 1)result = (result * base) % mod;
		base = (base * base) % mod;
		exp >>= 1;
	}
	return result;
}