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>
#include <fstream>
#include<chrono>
using namespace std;
using namespace chrono;
 
#define ll long long
#define db double
#define deb(x) cout<<#x<<": "<<x<<"\n"
#define all(x) x.begin(),x.end()
#define fo(i, n) for(i=0 ; i<n ; i++)
#define Fo(i, k, n) for(i=k ; i<n ; i++)
#define setBits(x) __builtin_popcountll(x)
#define parity(x) __builtin_parity(x)
 

void solve()
{
    int x;cin>>x;
    if(x>45)
    {
        cout<<-1<<endl;
        return;
    }

    int arr[10]={0};
    int n=x;
    for(int i=9;i>=1;i--)
    {
        if(n-i>=0)
        {
            arr[i]++;
            n-=i;
        }
    }
    //cout<<"Ans = ";
    for(int i=1;i<=9;i++)
    {
        if(arr[i]==1)
            cout<<i;
    }
    cout<<endl;

}




int32_t main() {
 
    int t;cin>>t;
    while(t--) solve();

    return 0;
}