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.Scanner;

//public class Ans
//{
//    static class Node{
//        int data ;
//        Node left , right ;
//        Node( int key )
//        {
//            data = key ;
//            left = right = null ;
//        }
//
//    }
//    Node head ;
//    Ans()
//    {
//        head = null ;
//    }
//    static Node insert( Node root , int key )
//    {
//        if( root == null )
//            return new Node(key);
//        if( key < root.data )
//        {
//            root.left = insert(root.left  , key );
//
//        }
//        else
//        {
//            root.right = insert( root.right , key );
//        }
//        return root ;
//    }
//    static void inorder( Node root)
//    {
//        if( root==null )
//            return ;
//        inorder( root.left );
//        System.out.print(root.data+" ");
//        inorder(root.right);
//    }
//    static Node delete( Node root , int key )
//    {
//        if( root == null )
//            return root ;
//        if( root.data > key )
//        {
//            root.left = delete( root.left , key );
//
//        }
//        else if( root.data < key )
//        {
//            root.right = delete( root.right , key );
//        }
//        else
//        {
//            if( root.left == null )
//                return root.right ;
//            else if( root.right == null )
//                return root.left ;
//            root.data = min_value( root.right);
//            root.right = delete ( root.right  , root.data );
//
//        }
//        return root ;
//    }
//
//
//
//}
public class Ans
{
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- > 0 ) {
        int n = sc.nextInt();
        int ans =0;
        if( n>= 1 && n<=9)
        {
            ans = n ;
        }
        else if( n>=10 && n <=17)
        {
            ans = 10*(n-9)+9;
        }
        else if(n>=18 && n<= 24)
        {
            ans = (n-17)*100+10*8+9;
        }
        else if(n>=25 && n<=30)
        {
            ans=(n-24)*1000+100*7+10*8+9;
        }
        else if( n>=31 && n<=35)
        {
            ans = (n-30)*10000+1000*6+100*7+10*8+9;
        }
        else if( n>=36 && n<=39)
        {
            ans = (n-35)*100000+10000*5+1000*6+100*7+10*8+9;
        }
        else if( n>=40 && n<=42)
        {
            ans = (n-39)*1000000+4*100000+10000*5+1000*6+100*7+10*8+9;
        }
        else if( n==43 )
        {
            ans = 13456789;
        }
        else if( n==44)
        {
            ans = 23456789;
        }
        else if( n==45)
        {
            ans = 123456789;
        }
        else
        {
            ans =-1;
        }
            System.out.println(ans);

                   }

    }
}