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.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while (t > 0) {
            int n = s.nextInt();
            String ans = func(n);
            System.out.println(ans);
            t--;
        }
    }

    private static String func(int n) {
        String ans = "";
        if (n > 45) {
            return "-1";
        }

        if (n <= 9) {
            return n + "";
        }

        if (n <= 17) {
            int diff = n - 9;
            return diff + "9";
        }

        if (n <= 24) {
            int diff = n - 17;
            return diff + "89";
        }

        if (n <= 30) {
            int diff = n - 24;
            return diff + "789";
        }

        if (n <= 35) {
            int diff = n - 30;
            return diff + "6789";
        }

        if (n <= 39) {
            int diff = n - 35;
            return diff + "56789";
        }

        if (n <= 42) {
            int diff = n - 39;
            return diff + "456789";
        }

        if (n <= 44) {
            int diff = n - 42;
            return diff + "3456789";
        }

        if (n == 45) {
            return "123456789";
        }
        return "";
    }
}