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 ll long long
#define ld long double
#define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define rint register int
#define mst(a,b) memset(a,b,sizeof(b))
#define FOR(i,x,y) for(rint i=x;i<y;i++)

using namespace std;
ll mod = 1000000007;
//typedef pair<int, int> pairs; 
bool prime(ll n)
{
	bool flag = 1;
	for(ll i=2; (ll)(i*i) <= n ;i++)
	{
		if(n%i == 0)
		{
			flag = 0;
			break;
		}
	}
	return flag;
}

void solve(int test)
{
	int x;
	cin>>x;

	string res = ""; 
	int num =9;

	if(x>45)
	{
		cout<<-1<<endl;
	}
	
	else
	{
		for(int i = 9;i>0;i--)
		{
			if(x>=i)
			{
				x-=i;
				res+=to_string(i);
			}
		}
		reverse(res.begin(),res.end());
		cout<<res<<endl;
	}
	

	// int a[n];

	// FOR(i,0,n)
	// {
	// 	cin>>a[i];
	// }

	
	//cout<<res<<endl;

	//cout<<"Case #"<<test<<": "<<ans<<endl;
}

int main()
{
	IOS;
	#ifndef ONLINE_JUDGE
	freopen("C:/Users/mnnh2/Desktop/cp resources/cp_template/codeforces/input.txt","r",stdin);
	freopen("C:/Users/mnnh2/Desktop/cp resources/cp_template/codeforces/output.txt","w",stdout);
	#endif

	// vector<bool> v(1000000,true);
	// vector<int> p;
	// 	for(ll i=2; ll(i*i)<1000000;i++)
	// 	{
	// 		for(ll (j)=i*i; j<1000000;j+=i)
	// 		{
	// 			v[j]=false;
	// 		}
	// 	}
	// 	for(int i=2;i<1000000;i++)
	// 	{
	// 		if(v[i]==true)
	// 			{
	// 				p.push_back(i);
	// 			}
	// 	}

	int t;
	cin>>t;
	int test = t;
	while(t--)
	{
		solve(test-t);	
	}

	// int n;
	// cin>>n;
	

	return 0;
}