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.util.*;

/**
 *
 * @author hriti
 */
public class C690 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        while (t-- > 0) {
            ArrayList<Integer> al = new ArrayList<>();
            int n = sc.nextInt();
            if(n == 50 || n == 49 || n == 48 || n == 47 || n == 46 )
            {
                System.out.println(-1);
                continue;
            }
            else
            {
                int i = 9;
                while(n >= i && i > 0)
                {
                   
                        al.add(i);
                        n = n - i;
                        i--;
                    
                }
                if( n > 0)
                al.add(n);
                for(int l = al.size()- 1; l >=0; l--)
                {
                    System.out.print(al.get(l));
                }
                System.out.println();
            }
                
            
            
            

        }

    }
}