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 final PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static final FastScanner fs = new FastScanner();
    private static final long MOD = (long) 998244353;

    public static void main(String[] args) throws IOException {
        int T = fs.nextInt();
        for(int i = 0 ; i < T ; i++){
            solve();
        }
        out.close();
    }
;
    static void solve(){
        int x = fs.nextInt();
        int digit = 9;
        int[] ans = new int[9];
        int ind = 0;
        while(x > 0 && digit > 0){
            if(digit <= x){
                ans[ind++] = digit;
                x -= digit;
            }
            digit--;
        }
        if( x == 0){
            for(int i = ind - 1; i >= 0 ; i--){
                out.print(ans[i]);
            }
            out.println(" ");
        }else{
            out.println(-1);
        }
    }

    static int lower_bound(Vector<Integer> a, int key){
        //assuming a is sorted
        int lb = 0;
        int rb = a.size();
//        System.out.println(rb);
        if( key <= a.get(lb)){
            return lb;
        }
        while(lb + 1 < rb){
            // a[lb][0] < key
            int m = (lb + rb) / 2;
            if(key <= a.get(m)){
                rb = m;
            }else{
                lb = m;
            }
        }
        return lb + 1;
    }
    static  class Point{
        public int x, y;
        public Point(){
            this(0, 0);
        }
        public Point(int a, int b){
            x = a;
            y = b;
        }
    }
    static class ModInt{
        private long n;
        public ModInt(){
            this(0L);
        }
        public ModInt(int n_){
            this((long) n_);
        }

        public ModInt(long n_){
            n = n_;
            if(n > MOD) {
                n = n % MOD;
            }else if ( n < 0){
                if(Math.abs(n) >= MOD){
                    n = n % MOD;
                }
                n += MOD;
            }
        }
        long getVal(){
            return n;
        }
        @Override
        public String toString() {
            return String.valueOf(n);
        }
        ModInt add(long rhs){
            long ans = this.n + rhs;
            return new ModInt(ans);
        }
        ModInt add(ModInt rhs){
            return this.add(rhs.getVal());
        }

        ModInt multiply(long rhs){
            long ans = this.n * rhs;
            return new ModInt(ans);
        }

        ModInt multiply(ModInt rhs){
            return this.multiply(rhs.getVal());
        }

        ModInt substract(long rhs){
            long ans = this.n - rhs;
            return new ModInt(ans);
        }

        ModInt substract(ModInt rhs){
            return this.substract(rhs.getVal());
        }

        ModInt pow(long n){
            if( n < 2){
                long ans = 1;
                for(int i = 0 ; i < n ; i++) ans *= this.n;
                return new ModInt(ans);
            }
            ModInt ans = this.pow(n/2);
            ans = ans.multiply(ans);
            if( n % 2 == 1) ans = ans.multiply(this);
            return ans;
        }
        ModInt pow(ModInt rhs){
            return  this.pow(rhs.getVal());
        }

        ModInt divide(long rhs){
            return this.divide(new ModInt(rhs));
        }

        ModInt divide(ModInt rhs){
            ModInt rhs_inverse = rhs.pow(MOD - 2);
            return this.multiply(rhs_inverse);
        }

    }
}
class data_container<T extends Comparable<T>> implements  Comparable<data_container<T>>{
    T first, second;
    public data_container(){
    }
    public data_container(T f, T s){
        first = f;
        second = s;
    }

    public T getComparableField(){
        return first;
    }

    @Override
    public int compareTo(data_container o) {
        return (int) this.getComparableField().compareTo((T) o.getComparableField()) ;
    }

    public int lower_bound(data_container[] a, T key){
        //assuming a is sorted
        int lb = 0;
        int rb = a.length;
        if( key.compareTo((T)a[lb].getComparableField()) <= 0){
            return lb;
        }
        while(lb + 1 < rb){
            // a[lb][0] < key
            int m = (lb + rb) / 2;
            if(key.compareTo((T) a[m].getComparableField()) <= 0){
                rb = m;
            }else{
                lb = m;
            }
        }
        return lb + 1;
    }

}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    public FastScanner(String s) {
        try {
            br = new BufferedReader(new FileReader(s));
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String nextToken() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(nextToken());
    }

    long nextLong() {
        return Long.parseLong(nextToken());
    }

    int[] readArray(int n){
        int[] a = new int[n];
        for(int i = 0 ; i < n ; i++) a[i] = nextInt();
        return a;
    }

    long[] readArrayLong(int n){
        long[] a = new long[n];
        for(int i = 0 ; i < n ; ++i) a[i] = nextLong();
        return a;
    }

    double nextDouble() {
        return Double.parseDouble(nextToken());
    }
}