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;

typedef long long int ll;
#define deb(x) cout << #x << " " << x << endl;
#define debtwo(x,y) cout << x << ", " << y << endl;
#define mod 1000000007
#define N 1000001

void solve() {
	ll n; cin >> n;

	if (n < 10) {
		cout << n << endl;
		return;
	}

	string res = "";
	ll val = 9;

	while (n) {
		res += to_string(min(val, n));
		n -= min(val, n);
		val -- ;
		if (val == 0) break;
	}

	if (n) {
		cout << -1 << endl;
		return;
	}

	reverse(res.begin(), res.end());

	cout << res << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll t = 1;
	cin >> t;

	while (t--) {
		solve();
	}
}