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:
//Created by Aminul on 12/16/2020.

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class HASH {
    static long res;

    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int test = in.nextInt();
        for (int t = 1; t <= test; t++) {
            int target = in.nextInt();

            pw.println(solveItr(target));
        }

        pw.close();
    }

    /*
        9876543210
        0101010011 -- MASK
     OR 0000000100
     ----------------
        0101010111

        00100
        2^x = 1 << x
     */

    static long solveItr(int target) {
        res = Long.MAX_VALUE;
        for(int i = 0; i < (1 << 10); i++) {
            long num = 0, sum = 0;
            for(int digit = 1; digit <= 9; digit++) {
                if(checkBit(i, digit)) {
                    sum += digit;
                    num = (num * 10) + digit;
                }
            }
            if(sum == target) {
                res = min(res, num);
            }
        }
        if (res == Long.MAX_VALUE) {
            res = -1;
        }
        return res;
    }

    static long solveRecursively(int target) {
        res = Long.MAX_VALUE;
        solve(0, 0, target, 0);
        if (res == Long.MAX_VALUE) {
            res = -1;
        }
        return res;
    }

    static void solve(int mask, int sum, int target, long num) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            res = min(res, num);
            return;
        }

        for (int i = 1; i <= 9; i++) {
            if (!checkBit(mask, i)) {
                solve(setBit(mask, i), sum + i, target, num * 10 + i);
            }
        }

    }

    static int setBit(int mask, int bit) {
        return (mask | (1 << bit));
    }

    static boolean checkBit(int mask, int bit) {
        int res = (mask & (1 << bit));
        return res == 0 ? false : true;
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }
}