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 ll long long 
#define db(x) cout << (#x) << " = " << x << "\n" ;
#define pb push_back
#define mt make_tuple
#define fr first
#define sc second
#define ull unsigned long long
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #ifndef ONLINE_JUDGE 
  freopen("input.txt", "r", stdin); 
  freopen("output.txt", "w", stdout); 
  #endif 
    ll t;
    cin >> t;
    while(t--){
      ll n;
      cin >> n;
      if(n>45) {
        cout << -1 << endl;
        continue;
      }
      string ans = "";
      ll curr = 9;
      while(n){
        if(curr >= n){
          char c = '0' + n;
          ans = c + ans;
          break;
        } else {
          char c = '0' + curr;
          ans = c + ans;
          n -= curr;
          curr--;
        }
      }
      cout << ans << endl;
    }
    return 0;
}