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 JAVA):

Solution:
import java.io.*;
import java.util.*;
 
 
public class NewClass {
    
    public static void main(String[] args)throws Exception{
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String in = br.readLine();
        int  t=Integer.parseInt(in);
        while(t-->0){
            String num = br.readLine();
            int n = Integer.parseInt(num);
           
            if(n>45){
                System.out.println(-1);
            }
            else{
                if(n<=9){
                    System.out.println(n);
                }
                else if(n<=17){
                    System.out.println((n-9)+""+9);
                }
                else if(n<=24){
                    System.out.println((n-17)+""+8+""+9);
                }
                else if(n<=30){
                    System.out.println((n-24)+""+7+""+8+""+9);
                }
                else if(n<=35){
                    System.out.println((n-30)+""+6+""+7+""+8+""+9);
                }
                else if(n<=39){
                    System.out.println((n-35)+""+5+""+6+""+7+""+8+""+9);
                }
                else if(n<=42){
                    System.out.println((n-39)+""+4+""+5+""+6+""+7+""+8+""+9);
                }
                else if(n<=44){
                    System.out.println((n-42)+""+3+""+4+""+5+""+6+""+7+""+8+""+9);
                }
                else if(n<=45){
                    System.out.println(1+""+2+""+3+""+4+""+5+""+6+""+7+""+8+""+9);
                }
            }
        }
        
    }
    
       
}