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 Main {
 
	//static int [] arr;
	//static boolean prime[] = new boolean[1000]; 
	//static List<Long> al = new ArrayList<>();
	//static int l;
	//static String s; static StringBuilder sb;
	//static HashSet<L> hs;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int t = sc.nextInt();
        //int t = 1;
        // sieve(600);
        while (t-->0) {
        	int x = sc.nextInt();
        	ArrayList<Integer> l = new ArrayList<Integer>();
        	int i = 9;
        	while(i>0) {
        		if(!l.contains(i) && i<=x) {
        			l.add(i);
        			x-=i;
        		}
        		i--;
        	}
        	if(x==0) {
        		for(int j = l.size()-1 ; j>=0 ;j--)
        			out.print(l.get(j));
        		out.println();
        	}
        	else {
        		out.println(-1);
        	}
    }


        
        	
        out.close();
    }
//    static boolean check(long n) {
//    	String s = n +"";
//    	for(int i = 0 ; i < s.length() ; i++) {
//    		if(s.charAt(i)=='0')
//    			continue;
//    		int x = Character.getNumericValue(s.charAt(i));
//    		if(n%x!=0)
//    			return false;
//    	}
//    	return true;
//    }
//    public static int solve(int arr[] , int n , int x) {
//    	if(isSorted(arr))
//    		return 0;
//    	int count = 0;
//    	for(int i = 0 ; i < n ; i++) {
//    		for(int j = 0 ; j < n ; j++) {
//    			if(x<arr[i]) {
//    				int temp = arr[i];
//    				arr[i] = x;
//    				x = temp;
//    				count++;
//    				if(isSorted(arr))
//    					return count;
//    			}
//    		}
//    	}
//    	return -1;
//    }
//    public static boolean isSorted (int [] arr) {
//    	for(int i = 0 ; i < arr.length -1 ; i++)
//    		if(arr[i]>arr[i+1])
//    			return false;
//    	return true;
//    }

     


        

    }

//    static void findsubsequences(String s, String ans){
//    	if (s.length() == 0) {
//    		if(ans!="")
//    			if(ans.length()!=l)
//    			al.add(Long.parseLong(ans));
//    		return;
//	}
//
//		// We add adding 1st character in string
//		findsubsequences(s.substring(1), ans + s.charAt(0));
//		
//		// Not adding first character of the string
//		// because the concept of subsequence either
//		// character will present or not
//		findsubsequences(s.substring(1), ans);
//}
    

    

    
//    static void sieve(int n) 
//    { 
//        // Create a boolean array "prime[0..n]" and initialize 
//        // all entries it as true. A value in prime[i] will 
//        // finally be false if i is Not a prime, else true. 
//        
//        for(int i=0;i<n;i++) 
//            prime[i] = true; 
//          
//        for(int p = 2; p*p <=n; p++) 
//        { 
//            // If prime[p] is not changed, then it is a prime 
//            if(prime[p] == true) 
//            { 
//                // Update all multiples of p 
//                for(int i = p*p; i <= n; i += p) 
//                    prime[i] = false; 
//            } 
//        } 
//    }
 //Print all prime numbers 
//        for(int i = 2; i <= n; i++) 
//        { 
//            if(prime[i] == true) 
//                System.out.print(i + " "); 
//        } 
    

 

    

	class Pair  implements Comparable <Pair>{
		int a ;
		int b ;
		public Pair(int a , int b) {
			this.a = a;
			this.b = b;
		}
		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			return this.a-o.a;
		}
		public String toString() {
			return "( " + this.a + " , " + this.b + " )\n";
		}
		
	}

	
	
	
	
	 class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public int[][] nextInt2DArr(int l, int w) throws IOException {
			int [][] arr = new int[l][w];
			for(int i = 0 ; i < l ; i++)
				for(int j = 0 ; j<w ; j++)
				arr[i][j]= Integer.parseInt(next());
			return arr;
		}

		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		public int[] nextIntArr(int length) throws IOException {
			int[] arr = new int[length];
			for(int i = 0 ; i < length ; i++)
				arr[i] = Integer.parseInt(next());
			return arr;
		}
		public boolean ready() throws IOException {
			return br.ready();
		}
	 }