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;
int main(){
  int t;
  cin>>t;
  while(t--){
    int x;
    cin>>x;
    if(x<10){
        cout<<x<<endl;
    }
    else if(x>45){
        cout<<-1<<endl;
    }
    else if(x>9&&x<=17){
        cout<<x-9<<9<<endl;
    }
    else if(x>17&&x<=24){
        cout<<x-17<<89<<endl;
    }
    else if(x>24&&x<=30){
        cout<<x-24<<789<<endl;
    }
    else if(x>30&&x<=35){
        cout<<x-30<<6789<<endl;
    }
    else if(x>35&&x<=39){
        cout<<x-35<<56789<<endl;
    }
    else if(x>39&&x<=42){
        cout<<x-39<<456789<<endl;
    }
    else if(x>42&&x<=44){
        cout<<x-42<<3456789<<endl;
    }
    else if(x>44&&x<=45){
        cout<<x-44<<23456789<<endl;
    }
  }
  return 0;
}