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
#define ull unsigned long long
#define fast_in_out  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ln "\n"
#define si(n) scanf("%d", &n);
#define pi(n) printf("%d\n", n);
#define sd(n) scanf("%lf", &n);
#define pd(n) printf("%.2lf\n", n);

const double EPS = (double) 1e-9;
const double pii = acos(-1);
const int mod = 1000000007;
const int N = (int) 1e5;

int main()
{
    fast_in_out;
    int test, num = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9;
    cin >> test;
    for(int t = 1; t <= test; t++)
    {
        int n, sum = 0;
        cin >> n;
        if(n < 10)
        {
            cout << n << ln;
            continue;
        }
        if(n > num)
        {
            cout << "-1" << ln;
            continue;
        }
        if(n == num)
        {
            cout << "123456789" << ln;
            continue;
        }
        int arr[10] = {0,0,0,0,0,0,0,0,0,0};
        for(int i = 9; i > 0; i--)
        {
            int x = sum + i;
            if(x <= n)
            {
                sum += i;
                arr[i]++;
            }
        }
        for(int i = 1; i < 10; i++)
        {
            if(arr[i])
            {
                cout << i;
            }
        }
        cout << ln;
    }
}