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 CodeForces {
	 static 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; 
	        } 
	    } 
	    
	    
	    public static void main(String[] args) 
	    { 
	        FastReader sc = new FastReader(); 
	        int t = sc.nextInt();
	        	while(t-->0) {
	        		int n = sc.nextInt();
	        		if(n<10) {
	        			System.out.println(n);
	        		}
	        		else if(n>45) {
	        			System.out.println("-1");
	        		}
	        		else {
	        			String str = "";
	        			for(int i=9;i>0;i--) {
	        				if(n<=9 && n<=i) {
	        					str += String.valueOf(n);
	        					n = 0;
	        					break;
	        				}else {
	        					str += String.valueOf(i);
	        					n -= i;
	        				}
	        			}
//	        			if(n == 0) {
//	        				System.out.println("-1");
//	        			}
//	        			else {
	        				StringBuilder sb=new StringBuilder(str);  
	        				System.out.println(sb.reverse());
//	        			}
	        		}
	        }
	    }
	}