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 ll long long 

int main(){
	
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    string s="";
	    int y=0;
	    int ans=0;
	    if(n>45)
	     ans=-1;
	    else
	     ans=1;
	     int k=0,z=0;
	    while(n>0 && ans){
	        if(n>=9-k){
	         y= (9-k) + y*10;
	         n=n-(9-k);
	         k++;
	        }
	        else{
	         y= n + y*10;
	         n=0;
	        }
	      // cout<<y<<endl;
	    }
	    while(y>0){
	         z=z*10 + (y%10);
	         y=y/10;
	      //   cout<<z<<" ";
	       }
	       
	    if(ans==1)
	     cout<<z<<endl;
	    else
	     cout<<"-1\n";
	}
}