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:

// Problem : C. Unique Number
// Contest : Codeforces - Codeforces Round #690 (Div. 3)
// URL : https://codeforces.com/contest/1462/problem/C
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair 
#define f(i,n) for(int i=0;i<n;i++) 
#define F first 
#define S second 
#define pb push_back 

using namespace std;

void test(){
	int n;
	cin>>n;
	if(n>45)cout<<"-1\n";
	else{
		int ans = 9;
		int low = 1, high = 9;
		while(low<=high){
			int mid = low + (high-low)/2;
			int sum = 0;
			for(int i=1;i<=mid;i++){
				sum = sum + (10-i);
			}
			if(sum>=n){
				ans = mid;
				high = mid - 1;
			}else
				low = mid + 1;
		}
		int arr[ans];
		for(int i=0;i<ans;i++)arr[i] = i+1;
		
		int sum = ans*(ans+1);
		sum = sum/2;
		
		int left = n - sum;
		// cout<<left<<"\n";
		int cur = 9;
		for(int i=ans-1;i>=0;i--){
			while(left>0 and arr[i]<cur){
				arr[i]++;
				left--;
			}
			cur--;
		}
		
		f(i,ans)cout<<arr[i];
		cout<<"\n";
		
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tests=1;
	cin>>tests;
	while(tests--){
		test();
	}
}