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 pb push_back
#define ppb pop_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef double d;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll, ll>> vpll;

const ll inf = 1e17 + 3;

int main() {
    ll t; cin >> t;
    while (t--) {
        ll x; cin >> x;
        if (x > 45) {
            cout << -1 << endl;
        } else {
            ll a = 9;
            str ans = "";
            while (x != 0) {
                if (x >= a) {
                    x = x - a;
                    ans = to_string(a) + ans;
                    a--;
                } else {
                    ans = to_string(x) + ans;
                    x = x - x;
                }
            }
            cout << ans << endl;
        }
    }
}