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:
/*
 * author : frija
 * c++ 17.12
*/

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

int check(int a)
{
    set <int> s;
    vector <int> v;
    int sum = 0;
    while (a > 0)
    {
        sum += a % 10;
        v.push_back(a%10);
        s.insert(a%10);
        a/= 10;
    }
    if (s.size() == v.size())
    {
        return sum;
    }
    else
    {
        return -1;
    }
}

void solve()
{
    int n;
    cin >> n;
    if (n > 45)
    {
        cout << "-1";
        return;
    }
    int a = 0;
    int st = 1;
    int last_av = 9;
    while (n > 0)
    {
        int cur = last_av;
        if (n < last_av)
        {
            cur = n;
        }
        a += st * cur;
        st *= 10;
        n -= cur;
        last_av --;
    }
    cout << a;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
        cout << "\n";
    }

}