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.Scanner;

public class UniqueNumber {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int tests = sc.nextInt();

        while(tests-- > 0)
        {
            int x = sc.nextInt();

            if(x < 10)
                System.out.println(x);

            else
            {
                if(x > 45)
                    System.out.println(-1);

                else
                {
                    String res;

                    if(x <= 17)
                        res = (x-9) + "9";

                    else
                    {
                        if(x <= 24)
                            res = (x-17) + "89";

                        else
                        {
                            if(x <= 30)
                                res = (x-24) + "789";

                            else
                            {
                                if(x <= 35)
                                    res = (x-30) + "6789";

                                else
                                {
                                    if(x <= 39)
                                        res = (x-35) + "56789";

                                    else
                                    {
                                        if(x <= 42)
                                            res = (x-39) + "456789";

                                        else
                                        {
                                            if(x == 43 || x == 44)
                                                res = (x-42) + "3456789";

                                            else
                                                res = "123456789";
                                        }
                                    }
                                }
                            }
                        }
                    }

                    System.out.println(res);
                }
            }
        }
    }
}