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 <math.h>
#define lli long long int
#include <limits.h>
#include <fstream>
#define F first
#define S second
#define PI 3.141592653589793238
#define pb push_back

using namespace std;

//doesn't work for arrays
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

/*const lli mod=1000000007;

lli gcd(lli a,lli b)
{
    if(a==0)
        return b;
    return gcd(b%a,a);
}

lli binpow(lli x,lli y,lli m)
{
    if (y==0)
        return 1;
    lli p=binpow(x,y/2,m)%m;
    p=(p*p)%m;
    if(y%2)
        return (x*p)%m;
    else
        return p;
}

lli modi(lli a,lli m)
{
    return binpow(a,m-2,m);
}*/

bool inside(int x,int n)
{
    if(x>=0 && x<n)
        return 1;
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli i,j,tt=1;
    cin>>tt;
    while(tt--)
    {
        int x,curr=9,pow=1;
        lli ans=0;
        cin>>x;
        if(x>45)
        {
            cout<<"-1\n";
            continue;
        }
        while(x>curr)
        {
            x-=curr;
            ans+=(pow*curr);
            pow*=10;
            curr--;
        }
        ans+=(pow*x);
        cout<<ans<<"\n";
    }
    return 0;
}