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.math.BigInteger;
import java.util.*;

public class test2{

    static boolean taken[] = new boolean[10]; 

    static StringBuilder rec(int pos, int sum, int x, StringBuilder str){
        if(sum == x)
            return str;
        if(pos > 8)
            return new StringBuilder("-1");
        
        for(int i=8; i>=1; i--){
            if(!taken[i]){
                taken[i] = true;
                str = str.append(i);
                StringBuilder ans = rec(pos+1, sum+i, x, str);
                if(!ans.toString().equals("-1"))
                    return ans;
                else{
                    taken[i]=false;
                    str = str.deleteCharAt(str.length()-1);
                }
            }
        }
        
        return new StringBuilder("-1");
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int x = sc.nextInt();
            if(x > 45){
                System.out.println(-1);
                continue;
            }
            int current = 9;
            StringBuilder sb = new StringBuilder();
            while(x > current){
                sb.append(current);
                x-=current--;
            }
            if(x > 0)
                sb=sb.append(x);
            System.out.println(sb.reverse());
            /*
            Arrays.fill(taken, false);
            StringBuilder result = rec(1, 9, x, new StringBuilder("9"));
            if(!result.toString().equals("-1")){
                System.out.println(printRev(result));
            }
            else{
                System.out.println("-1");
            }
            */
        }
        
        

        // System.out.println((n%2+1)*(n/2+1)*((n+1)/2+1));
       
    }

    static String printRev(StringBuilder sb){
        return sb.reverse().toString();
    }
}