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.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

/**
 * submission check list
 * 
 * @author david
 *
 */
public class Solution2 {

	static int mod = (int) 1e9 + 7;

	public static void main(String[] args) {
		FastScanner fs = new FastScanner();

		int T = fs.nextInt();

		while (T-- > 0) {
			int n = fs.nextInt();
			List<List<Integer>> res = new ArrayList<>();
			for (int i = 0; i < 1 << 10; i++) {
				int sum = 0;
				List<Integer> set = new ArrayList<>();
				for (int j = 0; j < 10; j++) {
					if (((1 << j) & i) > 0) {
						sum += j;
						set.add(j);
					}
				}
				if (sum == n) {
					res.add(set);
				}
			}
			
			List<Integer> x = new ArrayList<>();
			for (List<Integer> cand : res) { 
				Collections.sort(cand);
				StringBuilder sb = new StringBuilder();
				for (Integer cand2 : cand) {
					sb.append(cand2);
				}
				x.add(Integer.valueOf(sb.toString()));
			}
			
			Collections.sort(x);
			
			if (x.isEmpty()) {
				System.out.println(-1);
			} else {
				System.out.println(x.get(0));
			}
		}
	}

	static void sort(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

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

		int[] readArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

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

}