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 unsigned long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<ll, vector<ll>> vll;
#define ln "\n"
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())

int sumofdigit(int n)
{
  int sum = 0, m;
  set<int> s;
  while (n > 0)
  {
    m = n % 10;
    if (s.find(m) != s.end())
    {
      return -1;
    }
    s.insert(m);
    sum = sum + m;
    n = n / 10;
  }
  return sum;
}
void solve()
{
  int x;

  cin >> x;

  if (x < 10)
  {
    cout << x << endl;
    return;
  }

  if (x > 45)
  {
    cout << -1 << endl;
    return;
  }

  // for (int i = 10; i < 123456789; i++)
  // {
  //   int k = sumofdigit(i);
  //   if (k == x)
  //   {
  //     cout << i << endl;
  //     return;
  //   }
  // }

  int j = 9;
  int k = x;
  stack<int> v;

  while (k > j && j > 0)
  {
    k -= j;
    v.push(j);
    j--;
  }
  v.push(k);

  if (j == 0)
  {
    cout << -1 << endl;
    return;
  }

  while (!v.empty())
  {
    cout << v.top();
    v.pop();
  }
  cout << endl;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int test;
  cin >> test;
  for (int i = 1; i <= test; i++)
  {
    solve();
  }
  return 0;
}