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 main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin>>x;
        if(x<10)
        {
            cout<<x<<endl;
        }
        else if(x>45)
        {
            cout<<-1<<endl;
        }
        else
        {
            int sum=0;
            int flag=0;
            int k=9;
            while(k>0)
            {
                sum+=k;

                if(sum>=x)
                {
                    break;
                }
                k--;
            }
            int q=0;
            if(sum!=x)
            {
                q=k-(sum-x);
            }

            int i=0;
            for(int j=k; j<=9; j++)
            {
                if(q==0)
                {
                    i=10*i+j;
                }
                else
                {
                    if(flag==0)
                    {
                        i=q;
                        flag=1;
                    }
                    else
                    {
                        i=10*i+j;
                    }
                }
            }
            cout<<i<<endl;
        }
    }
    return 0;
}