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 int 		  	long long
#define f(i,n)        	for(int i=0;i<(n);++i)
#define fa(i,a,n)     	for(int i=a;i<=(n);++i)
#define fd(i,a,n)     	for(int i=a;i>=(n);--i)
#define tc 			  	int t;cin>>t;f(testcase,t)
#define ld				long double
#define pii             pair<int,int>
#define mem(a,i)		memset(a,i,sizeof(a))
#define all(x) 			x.begin(),x.end()
#define tr(c,i) 		for(auto i = c.begin(); i != c.end(); i++)
#define present(c,x) 	(c.find(x) != c.end())
#define cpresent(c,x) 	(find(allc,x) != c.end())
#define	PI 3.1415926535897932
void c_p_c() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
}

void solve() {
	int n;
	cin >> n;
	if (n > 45) {
		cout << "-1\n";
		return;
	}
	else {
		int i = 9;
		vector<int> ans;
		while (n > 0) {
			if (n >= i) {
				n -= i;
				ans.push_back(i);
			}
			--i;
		}
		sort(all(ans));
		for (auto x : ans)
			cout << x;
		cout << "\n";


	}
}

int32_t main() {

	c_p_c();

	tc
	solve();
	return 0;
}