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 long int lli;
int main()
{
	 #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        lli x;
        cin>>x;
        if(x>45)
            cout<<"-1"<<'\n';
        else 
        {
            if(x<10)
            {
                cout<<x<<'\n';
            }
            else 
            {
                if(x>9 && x<=17)
                {
                    cout<<x-9<<"9\n";
                }
                else if(x>17 && x<=24)
                {
                    cout<<x-17<<"89\n";
                }
                else if(x>24 && x<=30)
                {
                    cout<<x-24<<"789\n";
                }
                else if(x>30 && x<=35)
                {
                    cout<<x-30<<"6789\n";
                }
                else if(x>35 && x<=39)
                {
                    cout<<x-35<<"56789\n";
                }
                else if(x>39 && x<=42)
                    cout<<x-39<<"456789\n";
                else if(x>42 && x<=44)
                    cout<<x-42<<"3456789\n";
                else 
                    cout<<"123456789\n";

            }
                
        }

    }
}