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 FairDivision
{

    
    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);
        int t=scan.nextInt();       
        while(t-->0)
        { 
            int x=scan.nextInt();
            int g=0;
            int y=1,b;
            if(x>45)
            {
                System.out.println("-1");
            }
            
            else 
            {
                for(int i =9;i>0;i--)
                {
                    if(x>i)
                    {
                        x=x-i;
                        b=y*i;
                        g=g+b;
                        y=y*10;
                    }
                    else
                    {                        
                        g=g+(y*x);
                        System.out.println(g);
                        break;
                    }
                }
            }
            
        }
     
    }
    
}