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;
// typedef long l;
// typedef long long ll;
typedef vector<int> vi;
// typedef vector<char> vc;
typedef std::vector<int>::iterator Auto;
// #define PB push_back
#define FOR(i,a,b)  for(int i=a;i<b;i++)
#include <vector>




int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input","r",stdin); 		
    freopen("output","w",stdout);
    #endif

  	int t, x, sum, nn;
  	cin>>t;
  	FOR(i, 0, t){
  		cin>>x;
  		sum=0;
  		vector <int> v;
  		for(int j=9; j>=1; j--){
  			if(sum+j>x)
  				nn=0;
			else{
  				v.push_back(j);
  				sum=sum+j;
			}
  		}
  		sort(v.begin(), v.end());
  		if(sum==x){
  			for(auto &it:v)
  				cout<<it;
  		}
  		else
  			cout<<-1;
  		cout<<endl;
  	}
}