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.*;
public class A {
    public static void main(String[] args) {
        int t=0;
        Scanner sc=new Scanner(System.in);
        t=sc.nextInt();
        while(t-->0) {
           StringBuilder s=new StringBuilder("");
           int x=sc.nextInt();
           if(x>45) System.out.println(-1);
           
           else {
         for(int i=9;i>0;i--) {
             if(x>=i) {
                 s.append(i);
                 x-=i;
             }
         } }
            System.out.println(s.reverse());

        }
    }
}