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 Max 1000002
#define MOD 1e9 + 7
#define ll long long
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(s) (s).begin(), (s).end()
using namespace std;
void solve()
{
    ll n;
    cin >> n;
    if (n > 45)
    {
        cout << -1 << endl;
        return;
    }
    if (n <= 9)
    {
        cout << n << endl;
        return;
    }
    ll x = 9;
    string g = "";
    while (n != 0)
    {
        if (n - x < 0)
        {
            g += to_string(n);
            n = 0;
            --x;
        }
        else
        {
            n -= x;
            g += to_string(x);
            --x;
        }
    }
    reverse(all(g));
    cout << g << endl;
}
int main()
{
    fio;
    ll t;
    cin >> t;
    // ll t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}