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

public class UniqueNumber {

    public static void main(String[] args) {
        FastReader fr = new FastReader();

        int t = fr.nextInt();

        while (t-- > 0)
        {
            List<Integer> list = new ArrayList<>();
            int x = fr.nextInt();


            int sum = 0;
            int last = 9;

            while (sum < x && last > 0) {
                int added = Math.min((x-sum), last);
                list.add(added);
                last--;
                sum += added;
            }

            if (sum < x) {
                System.out.println(-1);
            } else {
                Collections.reverse(list);
                for (Integer i : list) {
                    System.out.printf("%d", i);
                }
                System.out.println();
            }
        }
    }


    // TLE
    private static void dfs(TreeSet<Integer> treeSet, int target, boolean[] used, int cur) {
        if (target == 0) {
            treeSet.add(cur);
            return;
        }

        for (int i = 9; i >= 0; i--) {
            if (cur == 0 && i == 0) continue;
            if (used[i]) continue;
            if (i > target) continue;
            used[i] = true;
            dfs(treeSet, target - i, used, cur * 10 + i);
            used[i] = false;
        }
    }

    public static class FastReader {

        private BufferedReader br;
        private StringTokenizer st;

        public FastReader() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

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

        long nextLong()
        {
            return Long.parseLong(next());
        }

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

        String nextLine()
        {
            String str = "";

            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }


    }
}