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>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#define ll long long int
#define mod 1000000007
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //code
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        if (n < 10)
            cout << n << "\n";
        else if (n > 45)
            cout << "-1\n";
        else
        {
            vector<int> arr;
            int num = 9;
            while (true)
            {
                if ((n >= num) && (n != 0))
                {
                    n = n - num;
                    arr.push_back(num);
                }
                else
                {
                    if (n != 0)
                        arr.push_back(n);
                    for (int i = arr.size() - 1; i >= 0; i--)
                        cout << arr[i];
                    cout << "\n";
                    break;
                }
                num -= 1;
            }
        }
    }
    return 0;
}