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;
int x;

void printArray(vector<int> arr, int n, set<int>&st) 
{ 
	int sum=0;
	string res="";
    for (int i = 0; i < n; i++) 
    { 
		sum+=arr[i];
		res+=to_string(arr[i]);
	}
	if(sum==x)
	{
		sort(res.begin(),res.end());
		st.insert(stoi(res));
	}

}

void printSubsequences(int arr[], int index,  
                       vector<int> subarr, set<int>&st) 
{ 

    if (index == 9) 
    { 
        int l = subarr.size(); 
        if (l != 0) 
            printArray(subarr, l, st); 
    } 
    else
    { 

        printSubsequences(arr, index + 1, subarr, st); 
        subarr.push_back(arr[index]); 
        printSubsequences(arr, index + 1, subarr, st); 
    } 
    return; 
} 

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>x;
		int arr[9] = {1,2,3,4,5,6,7,8,9};
		vector<int> subarray;
		set<int>st;
        printSubsequences(arr,0,subarray,st);
		if(st.size()==0)
		cout<<-1<<"\n";
		else
		cout<<*st.begin()<<"\n";
	}
				
}