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()
{
    double t, x, p;
    int check;
    cin>>t;
    while(t--){
        cin>>x;
        if(x>45){
            cout<<"-1\n";
            continue;
        }
        if(x<10){
            cout<<x<<"\n";
            continue;
        }
        if(x<18){
            cout<<x-9<<"9\n";
            continue;
        }
        if(x<25){
            cout<<x-17<<"89\n";
            continue;
        }
        if(x<31){
            cout<<x-24<<"789\n";
            continue;
        }
        if(x<36){
            cout<<x-30<<"6789\n";
            continue;
        }
        if(x<40){
            cout<<x-35<<"56789\n";
            continue;
        }
        if(x<43){
            cout<<x-39<<"456789\n";
            continue;
        }
        if(x<45){
            cout<<x-42<<"3456789\n";
            continue;
        }
        else
            cout<<x-44<<"23456789\n";



    }
return 0;
}