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
#define pb push_back
#define eb emplace_back
#define precision(n) cout << fixed << setprecision(n);
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin>>x;
         if(x<10)
        {
            cout<<x<<endl;
        }
        else if(x>=10&&x<=20)
        {
            if(x==10)
            {
                cout<<19<<endl;
            }
            else if(x==11)
            {
                cout<<29<<endl;
            }
            else if(x==12)
            {
                cout<<39<<endl;
            }
            else if(x==13)
            {
                cout<<49<<endl;
            }
            else if(x==14)
            {
                cout<<59<<endl;
            }
            else if(x==15)
            {
                cout<<69<<endl;
            }
            else if(x==16)
            {
                cout<<79<<endl;
            }
            else if(x==17)
            {
                cout<<89<<endl;
            }
            else if(x==18)
            {
                cout<<189<<endl;
            }
            else if(x==19)
            {
                cout<<289<<endl;
            }
            else if(x==20)
            {
                cout<<389<<endl;
            }
        }
        else if(x>20&&x<=45)
        {
           if(x==21)
            {
                cout<<489<<endl;
            }
            else if(x==22)
            {
                cout<<589<<endl;
            }
            else if(x==23)
            {
                cout<<689<<endl;
            }
            else if(x==24)
            {
                cout<<789<<endl;
            }
            else if(x==25)
            {
                cout<<1789<<endl;
            }
            else if(x==26)
            {
                cout<<2789<<endl;
            }
            else if(x==27)
            {
                cout<<3789<<endl;
            }
            else if(x==28)
            {
                cout<<4789<<endl;
            }
            else if(x==29)
            {
                cout<<5789<<endl;
            }
            else if(x==30)
            {
                cout<<6789<<endl;
            }
            else if(x==31)
            {
                cout<<16789<<endl;
            }
            else if(x==32)
            {
                cout<<26789<<endl;
            }
            else if(x==33)
            {
                cout<<36789<<endl;
            }
            else if(x==34)
            {
                cout<<46789<<endl;
            }
            else if(x==35)
            {
                cout<<56789<<endl;
            }
            else if(x==36)
            {
                cout<<156789<<endl;
            }
            else if(x==37)
            {
                cout<<256789<<endl;
            }
            else if(x==38)
            {
                cout<<356789<<endl;
            }
            else if(x==39)
            {
                cout<<456789<<endl;
            }
            else if(x==40)
            {
                cout<<1456789<<endl;
            }
            else if(x==41)
            {
                cout<<2456789<<endl;
            }
            else if(x==42)
            {
                cout<<3456789<<endl;
            }
            else if(x==43)
            {
                cout<<13456789<<endl;
            }
            else if(x==44)
            {
                cout<<23456789<<endl;
            }
            else if(x==45)
            {
                cout<<123456789<<endl;
            }
        }
        else
        {
            cout<<-1<<endl;
        }
    }
    return 0;
}