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;

#define INF 1000000000
#define INFLL 0x3f3f3f3f3f3f3f3fLL 
#define EPS 10e-9
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define st first
#define nd second
#define sz(v) int(v.size())
#define all(X) (X).begin(), (X).end()
#define FOR(I, A, B) for(int I = A; I < B; I++)
#define RFOR(I, A, B) for(int I = A; I >= B; I--)

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<iii> viii;
typedef vector<ll> vll;


int test(int mask){
	int ans = 0;
	for(int i = 0; i < 9; i++){
		if((1<<i) & mask){
			ans*=10;
			ans+=(1+i);
		}
	}
	return ans;
}

int sum_dig(int val){
	int ans = 0;
	while(val > 0){
		ans += (val%10);
		val /= 10;
	}
	return ans;
}

int solvre(int x){
	
	vector<int> ans;
	for(int mask = 0; mask < 1<<10; mask++){
		int val = test(mask);
		if(sum_dig(val) == x){
			ans.pb(val);
		}
	}

	sort(all(ans));

	if(sz(ans) == 0) return -1;
	return ans[0];
}

int main(){
	int t;
	cin >> t;
	while(t--){
		int x;
		cin >> x;
		cout << solvre(x) << endl;
	}
	return 0;
}