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 unique {
    public static void main(String[] args) throws java.io.IOException {
        File file = new File("hoofball.in"); // change this
        Scanner input = new Scanner(System.in); // change this
        PrintWriter output = new PrintWriter("hoofball.out"); // change this or ph

        int testcases = input.nextInt();
        for (int t = 0; t < testcases; t++) {
            int number = input.nextInt();
            int counter = 0;
            int maxcounter = 9;
            ArrayList<Integer> digits = new ArrayList<Integer>();
            if (number <= 45) {
                loop:
                while (counter < number) {
                    int newdigit = 0;
                    for (int i = 0; i < maxcounter; i++) {
                        newdigit++;
                        counter++;
                        if (counter >= number) {
                            digits.add(newdigit);
                            break loop;
                        }
                    }
                    digits.add(newdigit);
                    maxcounter--;
                }
                for (int i = digits.size() - 1; i >= 0; i--) {
                    System.out.print(digits.get(i));
                }
                System.out.println();
            } else {
                System.out.println(-1);
            }

        }

        output.close();
    }
}