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<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
int t, n;

inline void solve(int x)
{
	if (x >= 1 && x <= 9) {
		cout << x << endl;
		return;
	}
	if (x > 45) {
		cout << "-1" << endl;
		return;
	}
	int s[20]; int m = 0; int lim = 9;
	while ((x - lim) > 0&&x) {
		s[m] = lim; m++;
		x -= lim;
		lim--;
	}
	s[m++] = x;
	if (s[m - 1] == 0) {
		cout << s[m - 2] << s[m - 1];
		for (int i = m - 3; i >= 0; i--)cout << s[i];
		cout << endl;
	}
	else
	{
		for (int i = m - 1; i >= 0; i--)cout << s[i];
		cout << endl;
	}
	return;
}
int main() {
	IOS
		cin >> t;
	while (t--)
	{
		cin >> n;
		solve(n);
	}
	return 0;
}