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 number(int x){
    if(x<10)return x;
    if(x>45)return -1;
    string s="";
    int num=9;
    while(x>0 && num>0){
        if(num>x)num=x;
        s+=to_string(num);
        x-=num;
        num--;
    }
    
    
    reverse(s.begin(),s.end());
    
    return stoi(s);
}

int main() {
	int t;
	cin>>t;
	while(t--){
	    int x;
	    cin>>x;
	    cout<<number(x)<<endl;
	}
	return 0;
}