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 abc1
{
   public static void main(String args[])
   {
      try
      {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
         int n=sc.nextInt();
         String s="";
         if(n>=9)
         {
             n-=9;
             s="9"+s;
            }
         if(n>=8)
            {
                n-=8;
                s="8"+s;
            }
         if(n>=7)
            {
                n-=7;
                s="7"+s;
            }
         if(n>=6)
            {
                n-=6;
                s="6"+s;
            }
            if(n>=5)
            {
                n-=5;
                s="5"+s;
            }
            if(n>=4)
            {
                n-=4;
                s="4"+s;
            }
            if(n>=3)
            {
                n-=3;
                s="3"+s;
            }
            if(n>=2)
            {
                n-=2;
                s="2"+s;
            }
            if(n>=1)
            {
                n-=1;
                s="1"+s;
            }
            if(n==0)
            System.out.println(s);
            else
            System.out.println("-1");
    }
    
      }
      catch(Exception e)
      {
           
      }
   }
}