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:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<map>
#include<fstream>
#include<queue>
#include<time.h>
#include<unordered_map>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;
const int MAX_N = 300 + 5;

int a[51];

void init() {
	for (int i = 0; i <= 50; i++)a[i] = 1e9;
	for (int i = 0; i < (1 << 9); i++) {
		int s = 0, p = 0;
		for (int j = 0; j < 9; j++) {
			if ((i & (1 << j)) == 0)continue;
			s += j + 1;
			p = p * 10 + j + 1;
		}
		if (s <= 50)a[s] = min(a[s], p);
	}
}

int main() {
	int T;
	cin >> T;
	init();
	while (T--) {
		int x;
		cin >> x;
		if (a[x] == 1e9)cout << -1 << endl;
		else cout << a[x]<<endl;
	}
	return 0;
}