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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1462C {

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);

        int tests = Reader.nextInt();
        for(int t = 0; t < tests; t++) {
            System.out.println(solve());
        }
    }

    private static int solve() throws IOException {
        int x = Reader.nextInt();

        if (x < 9) {
            return x;
        } else if (x > 45) {
            return -1;
        }

        for(int l = 1; l <= 9; l++) {
            int res = solve(0, 0, l, 0, 0, x);
            if (res > -1) {
                return res;
            }
        }

        return -1;
    }

    private static int solve(int start, int curLen, int maxLen, int num, int sum, int x) {
        if (sum == x) {
            return num;
        }
        if (sum > x || curLen == maxLen) {
            return -1;
        }

        for(int i = start + 1; i <= 9; i++) {
            int res = solve(i, curLen + 1, maxLen, num * 10 + i, sum + i, x);
            if (res != -1) {
                return res;
            }
        }

        return -1;
    }
}

/** Class for buffered reading int and double values */
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

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

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}