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.io.*;
import java.util.*;
 public class Solution {
	 public static void main(String[] args) throws Exception
    {
		FastReader fr=new FastReader();
		
	
        int t=fr.nextInt();
        while(t-->0) {
        	int x=fr.nextInt();
             if(x>45)
            	 System.out.println(-1);
             else {
            	 boolean found=false;
            	 int cur=9;
            	 String str="";
            	 while(x>cur) {
            		 str=cur+str;
            		 x-=cur;
            		 cur--;
            	 }
            	
            		 System.out.println(x+str);
             }
           
          
            
           
        }
    } 
	 
 }
 class Pair implements Comparable<Pair>{
	 int x,y;
	 Pair(int x,int y){
		 this.x=x;
		 this.y=y;
	 }
	@Override
	public int compareTo(Pair o) {
		return (this.y-o.y);
	}
 }
  

class FastReader
{
    BufferedReader br;
    StringTokenizer st;
 
    public FastReader()
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }
 
    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
 
    int nextInt()
    {
        return Integer.parseInt(next());
    }
 
    long nextLong()
    {
        return Long.parseLong(next());
    }
 
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
 
    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}