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:
//In the name of God
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N = 500 + 10;
int t, n;
vector<int> v;

void read_input() {
	cin >> n;
}

void solve() {
	v.clear();
	int sum = 0;
	if (n > 45) {
		cout << -1 << '\n';
		return;
	}
	for (int i = 9; i; i--) {
		sum += i;
		if (sum == n) {
			v.push_back(i);
			reverse(v.begin(), v.end());
			for (int u: v)
				cout << u;
			cout << '\n';
			return;
		}
		else if (sum > n) {
			sum -= i;
			v.push_back(n - sum);
			reverse(v.begin(), v.end());
			for (int u: v)
				cout << u;
			cout << '\n';
			return;
		}
		v.push_back(i);
	}
}

int main() {
	int cnt = 0;
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		read_input();
		solve();
	}
}