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 ld long double
#define sout(x) cout << #x << " is : " << x << '\n';
#define pqmax priority_queue<ll>
#define pqmin priority_queue<ll, vt<ll>, greater<ll>>
#define setbits(x) __builtin_popcountll(x)
#define ps(x, y) fixed << setprecision(y) << x
#define EACH(x, a) for (auto &x : a)
#define FOR(var, start, size) for (ll var = start; var < size; var++)
#define tc()  \
    int t;    \
    cin >> t; \
    while (t--)
const ll modo = 1e9 + 7;
const ll INF = 1e17;
const ll ms = 1e5 + 5;
void cp()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void solve(){
    int N;
    cin >> N;
    if(N > 45){
        cout << "-1\n";
        return;
    }
    string s = "";
    for (int i = 9; i >= 1; i--)
    {
        if(N <= 9 and N <= i){
            // cout << N;
            s += to_string(N);
            N = 0;
            break;       
        }
        else{
            // cout << i;
            // s+=i;
            s += to_string(i);
            N-=i;
        }
    }
    if(N){
        cout << "-1\n";
        return;
    }
    // s.reserve();
    reverse(s.begin(), s.end());
    cout << s << endl; 

    
}
int main()
{
    cp();
    tc(){
        solve();
    }
    return 0;
}