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:
// magneto_19
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;

void solve() {
	int n;
	cin >> n;
	if (n > 45) {
		cout << -1 << endl;
		return;
	}
	if (n / 10 == 0) {
		cout << n << endl;
		return;
	}
	set<int> ans;
	int i = 9;
	while (1) {
		if (n < 9) {
			if (ans.find(n) == ans.end()) {
				ans.insert(n);
				break;
			}
		}
		n -= i;
		ans.insert(i);
		i--;
	}

	for (auto i : ans) {
		cout << i;
	}
	cout << endl;
}

int main() {

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

	return 0;
}