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.*;
import java.math.*;
import java.util.stream.Collectors;
import java.util.stream.*;

public class Main { 

    static ArrayList<ArrayList<Integer>> al;
    static boolean[][] dp;
    
    public static void main(String[] args) throws java.lang.Exception { 
        Reader pm =new Reader(); 

        //Scanner pm = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int t = pm.nextInt();
        while(t-- > 0){
            int sum = pm.nextInt();
            al = new ArrayList<>();

            int[] arr = {1,2,3,4,5,6,7,8,9};
            int n = arr.length;
            //int sum = n;

            dp = new boolean[n][sum + 1]; 
            for (int i=0; i<n; ++i) { 
                dp[i][0] = true; 
            } 
        
            if (arr[0] <= sum) 
                dp[0][arr[0]] = true; 
        
            for (int i = 1; i < n; ++i) {
                for (int j = 0; j < sum + 1; ++j) {
                    if(arr[i] <= j) {
                        dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i]];
                    }
                    else
                        dp[i][j] = dp[i-1][j];
                }
            }
            if (dp[n-1][sum] == false) { 
                System.out.println(-1);
                continue;
            } 
            ArrayList<Integer> p = new ArrayList<>(); 
            printSubs(arr, n-1, sum, p); 

            ArrayList<Long> ans = new ArrayList<>();
            //System.out.println(al);
            for(int i = 0; i < al.size(); i++) {
                ArrayList<Integer> pl = al.get(i);
                Collections.sort(pl);
                StringBuffer sb = new StringBuffer();
                for(int j =0; j< pl.size();j++)
                    sb.append(pl.get(j));
                long num = Long.parseLong(sb.toString());
                ans.add(num);
            }
            Collections.sort(ans);
            //System.out.println(ans);

            if(ans.size() == 0) {
                System.out.println(-1);
                continue;
            }
            System.out.println(ans.get(0));
        }
        
    }
    
    static void printSubs(int arr[], int i, int tot, ArrayList<Integer> pl) { 

        if (i == 0 && tot != 0 && dp[0][tot]) { 
            pl.add(arr[i]); 
            al.add(pl);
            pl = new ArrayList<>();
            return; 
        } 
    
        if (i == 0 && tot == 0) { 
            al.add(pl);
            pl = new ArrayList<>();
            return; 
        } 
    

        if (dp[i-1][tot]) { 
            ArrayList<Integer> bbn = new ArrayList<>(); 
            bbn.addAll(pl); 
            printSubs(arr, i-1, tot, bbn); 
        } 
    
 
        if (tot >= arr[i] && dp[i-1][tot-arr[i]])  { 
            pl.add(arr[i]); 
            printSubs(arr, i-1, tot-arr[i], pl); 
        } 
    } 


    // function to count elements within given range 
    static int countInRange(int arr[], int n, int x, int y) { 
        // initialize result 
        int count = 0; 
        count = upperIndex(arr, n, y) -  
                lowerIndex(arr, n, x) + 1; 
        return count; 
    } 
    
    
    static int lowerIndex(int arr[], int n, int x) { 
        int l = 0, h = n - 1; 
        while (l <= h)  
        { 
            int mid = (l + h) / 2; 
            if (arr[mid] >= x) 
                h = mid - 1; 
            else
                l = mid + 1; 
        } 
        return l; 
    } 
      
    // function to find last index <= y 
    static int upperIndex(int arr[], int n, int y) { 
        int l = 0, h = n - 1; 
        while (l <= h)  
        { 
            int mid = (l + h) / 2; 
            if (arr[mid] <= y) 
                l = mid + 1; 
            else
                h = mid - 1; 
        } 
        return h; 
    }
    
    public static StringBuilder dec_to_bin(long n) {
        // decimal to binary upto 30 binaries
        if(n==0) {
            StringBuilder str=new StringBuilder("");
            for(int i=0;i<30;i++) {
                str.append("0");
            }
            return str;
        }
        StringBuilder str=new StringBuilder("");
        while(n!=0) {
            str.append(n%2L);
            n/=2L;
        }
        str=str.reverse();
        StringBuilder tmp_str=new StringBuilder("");
        int len=str.length();
        while(len!=30) {
            tmp_str.append("0");
            len++;
        }
        tmp_str.append(str);
        return tmp_str;
    }
    
    private static int binarySearchPM(int[] arr, int key){
        int n = arr.length;
        int mid = -1;
        int begin = 0,end=n;
        while(begin <= end){
            mid = (begin+end) / 2;
            if(mid == n){
                return n;
            }
            if(key < arr[mid]){
                end = mid-1;
            } else if(key > arr[mid]){
                begin = mid+1;
            } else {
                return mid;
            }
        }
        //System.out.println(begin+" "+end);
        return -begin; //expected Index
    }
    
    private static List<Integer> setToList(Set<Integer> s){
        List<Integer> al = s.stream().collect(Collectors.toList());
        return al;
    }
    
    private static List<Integer> mapValToList(HashMap<Integer,Integer> map){
        return map.values().stream().collect(Collectors.toList());
    }
    
    private static List<Integer> mapKeyToList(HashMap<Integer,Integer> map){
        return map.keySet().stream().collect(Collectors.toList());
    }
    
    private static HashMap<Integer, Integer> sortByKey(HashMap<Integer,Integer> map){
        return map
                .entrySet()
                .stream()
                .sorted(Map.Entry.comparingByValue())
                .collect(Collectors.toMap(
                    Map.Entry::getKey, 
                    Map.Entry::getValue, 
                    (oldValue, newValue) -> oldValue, LinkedHashMap::new));
    }
    
    static class Reader { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    }
}