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>

#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define pii pair < int, int >
#define pll pair < long long, long long >
#define ull unsigned long long
#define pi 3.1415926536
#define y1 wjfhszuf

using namespace std;

const int inf = (int)(1e9 + 7);
const ll INF = (ll)(1e18 + 7);
const int mod = (int)(1e9 + 7);
const ll MOD = (ll)(1e18 + 7);
const int N = (int)(1e5 + 500);

int t;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> t;
    while (t--)
    {
        int x;
        vector < int > ans;
        ans.clear();
        cin >> x;
        if (x > 45)
        {
            cout << "-1\n";
            continue;
        }
        
        int i = 9;
        while (x >= i && i > 0)
            ans.pb(i), x -= i, i--;
        if (x > 0)
            ans.pb(x);
        for (int i = (int)ans.size() - 1; i >= 0; i--)
            cout << ans[i];
        cout << '\n';
    }
    return 0;
}