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 <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include<set>
#include<unordered_set>
#include<iomanip>
#include<queue>
#include<unordered_map>
#include<fstream>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define V vector
#define FOR1(i,a,b) for(int i=a; i<b; i++)
#define FOR(i,a) for (int i=0; i<a; i++)

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		V<int>digit;
		if (n > 45) {
			cout << -1 << endl;
		}
		else {
			int counter = 9;
			while (counter>0 && n > 0) {
				if (n >= counter) {
					n -= counter;
					digit.push_back(counter);
				}
				counter--;
			}
			if (n != 0) {
				cout << -1 << endl;
			}
			else {
				reverse(digit.begin(), digit.end());
				for (auto k : digit) {
					cout << k;
				}
				cout << endl;
			}
		}
	}
}