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;
typedef long long ll;
typedef long double ld;
const ll mod = 1e9+7;
#define el "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.14159265358
#define F first
#define S second
#define pb push_back 
#define mp make_pair
#define f(i,x,y) for(i=x;i<y;i++) 
#define fo(i,x,y) for(i=x;i>=y;i--)
#define all(v) v.begin(),v.end()
#define ss(v) sort(all(v))
//cout<<setprecision(9);
// sieve
/*bool prime[100000];
void sieve(ll n) 
{ 
    
    memset(prime, true, sizeof(prime)); 
    for (ll p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (ll i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
    

}
*/
void solve(){
int x; cin >> x;
 
    if(x > 45) {
        cout << -1 << endl;
        return;
    }
 
    string ans = "";
    
    for(int i = 9; i >= 1 && x > 0; i --) {
 
        if(i <= x) {
            ans = (char)(i + '0') + ans;
            x -= i;
        }
    }
 
    cout << ans << endl;
}

int main() {
fastio
ll _;
//_=1;
cin>>_;
while(_--)
{
solve();
}
return 0;
}