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 rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define per(i, n) for(int i = n - 1; i >= 0; --i)
#define per1(i, n) for(int i = n; i >= 1; --i)
#define ll long long int
#define fok(i, k, n) for(int i = k; i < n; ++i)
#define all(X) X.begin(), X.end()
#define pb push_back
#define present(a, x) (a.find(x)!=a.end())
#define MOD 1e9+7
#define mk make_pair
#define deb(x) cout << #x << " " << (x) << "\n";

using namespace std;
typedef vector<int> vi;
typedef vector< vector<int> > vii;
typedef pair<int, int> pi;

bool check(int val) {
    int cnt = 0;
    set<int> s;
    while(val > 0) {
        cnt++;
        s.insert(val%10);
        val /= 10;
    }
    return cnt == s.size();
}
int get_sum(vector<int> x) {
    int ans = 0;
    for(int i = 0; i < x.size(); ++i) {
        ans += x[i];
    }
    return ans;
}


int get_num(vector<int> a) {
    int num = 0;
    int p = 0;
    sort(a.begin(), a.end());
    for(int i = a.size() - 1; i >= 0; --i) {
        num += a[i] * pow(10, p);
        p++;
    }
    return num;
}



void subsetsUtil(vector<int>& A, vector<vector<int> >& res, 
                 vector<int>& subset, int index) 
{ 
    res.push_back(subset); 
    for (int i = index; i < A.size(); i++) { 
  
        // include the A[i] in subset. 
        subset.push_back(A[i]); 
  
        // move onto the next element. 
        subsetsUtil(A, res, subset, i + 1); 
  
        // exclude the A[i] from subset and triggers 
        // backtracking. 
        subset.pop_back(); 
    } 
  
    return; 
} 
  
// below function returns the subsets of vector A. 
vector<vector<int> > subsets(vector<int>& A) 
{ 
    vector<int> subset; 
    vector<vector<int> > res; 
  
    // keeps track of current element in vector A; 
    int index = 0; 
    subsetsUtil(A, res, subset, index); 
  
    return res; 
}


int main() {
    int t = 1;
    cin >> t;
    vector<int> ans(51, -1);
    vector<int> a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    vector<vector<int>> sub = subsets(a);
    // for(vector<int> x : sub) {
    //     for(int i : x) {
    //         cout << i << " ";
    //     }
    //     cout << endl;
    // }

    for(vector<int> x : sub) {
        int sum = get_sum(x);
        int num = get_num(x);
        if(ans[sum] == -1 || ans[sum] > num) {
            ans[sum] = num;
        }
    }
    while(t--){
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
    return 0;
}