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>
#define endl '\n'
#define modulo 1000000007
#define ll long long
#define PI acos(-1)
#define pk push_back
//#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#define sinDegrees(x) sin((x) * PI / 180.0)
#define cosDegrees(x) cos((x) * PI / 180.0)
#define tanDegrees(x) tan((x) * PI / 180.0)
#define atanDegrees(x) atan(x)* 180.0 / PI
#define asinDegrees(x) asin(x)* 180.0 / PI
#define EPS 0.000000001
#define ff first
#define ss second
using namespace std;
ll abs(ll w ,ll v)
{
	return (max(w ,v)-min(w ,v));
}
 
bool vis[10] = {false} ;
ll ans=-1 ;

void dp(int n ,ll cur ,int sum)
{
	
	if(sum==n)
	{
		if(ans!=-1)
		ans=min(cur ,ans ) ;
		if(ans==-1)
		ans = cur ; 
		return ;
	}
	
	for(int i=1 ; i<=9 ;i++  )
	{
		if(!vis[i])
		{
			vis[i]=1 ;
			dp( n,(cur*10)+i ,sum+i);
			vis[i] =0 ;
		}
	
	}
	
}
 
 
void solve()
{
	int n ;
	scanf("%d" ,&n) ;
 
		dp(n ,0 ,0);
		printf("%lld\n" ,ans);
		memset(vis ,false ,sizeof(vis));
		ans=-1 ;
 
}
int main()
{
		int i=1 ;
		cin>>i;
		while(i--) solve();
}