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:
//Krunal_Mathukiya
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define li long int
#define pb push_back
#define mkp make_pair
#define nikalL return
#define chalavo continue
#define basHo break
#define saaf clear
#define umap unordered_map
#define F first
#define S second
#define vi vector<int>
#define pii pair<int,int>
#define fr(i,s,n) for(int i=s;i<=n;++i)
#define frr(i,s,n) for(int i=s;i>=n;--i)
#define jaldiKarNe ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
lli n,m,l,r,x;
lli arr[1000006];
vi g[1000006];
void TestingChaluKarEyy(){
	cin>>n;
	if(n<=9) {
		cout<<n<<"\n";
		nikalL;
	}
	vi ans;
	int pivot=9;
	while(n>pivot) {
		ans.pb(pivot);
		n-=pivot;
		pivot--;
		if(!pivot && n) {
			cout<<"-1\n";
			nikalL;
		}
	}
	ans.pb(n);
	reverse(ans.begin(),ans.end());
	for(auto x:ans) cout<<x;
	cout<<"\n";
}
void sublime() {
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
}
int main(){
//	sublime();
	jaldiKarNe;
	int TestingKaravvuChhe=1;
	cin>>TestingKaravvuChhe;
	while(TestingKaravvuChhe--){
		TestingChaluKarEyy();
	}
}