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;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define take(x,n); vector<x> v(n); for(auto &i:v) cin>>i;

int main()
{
    fast;
    int t; cin>>t;
    while(t--){
        long s=0,i=1;
        int x; cin>>x;
        if(x<=9){
             cout<<x<<"\n"; x=0;
        }
        else if(x>=10 && x<=17) {
            cout<<(x-9)<<"9\n";
        }
        else if(x>=18 && x<=24) {
            cout<<(x-17)<<"89\n";
        }
        else if(x>=25 && x<=30) {
            cout<<(x-24)<<"789\n";
        }
        else if(x>=31 && x<=35) {
            cout<<(x-30)<<"6789\n";
        }
        else if(x>=36 && x<=39) {
            cout<<(x-35)<<"56789\n";
        }
        else if(x>=40 && x<=42) {
            cout<<(x-39)<<"456789\n";
        }
        else if(x>=43 && x<=44) {
            cout<<(x-42)<<"3456789\n";
        }
        else if(x>=45&& x<=45) {
            cout<<"123456789\n";
        }
        else cout<<"-1\n";
    }
    return 0;
}