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.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Contest {

	static final Random random = new Random();

	static PrintWriter out = new PrintWriter(System.out);

	private static boolean[] vis = new boolean[10];

	private static TreeSet<Long> res = new TreeSet<>();

	static int sum(long x) {
		int res = 0;
		while (x != 0) {
			res += x % 10;
			x /= 10;
		}
		return res;
	}

	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(System.in);

		long[] res1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 189, 289, 389, 489, 589, 689, 789,
				1789, 2789, 3789, 4789, 5789, 6789, 16789, 26789, 36789, 46789, 56789, 156789, 256789, 356789, 456789,
				1456789, 2456789, 3456789, 13456789, 23456789, 123456789 };
		
		Arrays.sort(res1);

//		run(0);
//		ArrayList<Long> arr = new ArrayList<>();
//
//		for (int i = 1; i <= 50; i++) {
//			for (long x : res) {
//				if (sum(x) == i) {
//					arr.add(x);
//					break;
//				}
//			}
//		}

//		System.out.println(arr);

		int tc = sc.nextInt();

//		System.out.println(res.size());

		while (tc-- > 0) {
			int n = sc.nextInt();
			boolean found = false;

			for (long x : res1) {
				if (sum(x) == n) {
					found = true;
					out.println(x);
					break;
				}
			}

			if (!found)
				out.println(-1);

		}

		out.flush();
	}

	static char[] ans = new char[10];

	static void run(int stop) {

		long temp = 0;
		for (int i = 0; i < 10; i++) {
			if (ans[i] >= '0') {
				temp *= 10;
				temp += (long) (ans[i] - '0');
			}
		}

		res.add(temp);

		if (stop == 10)
			return;

		for (int i = 0; i < 10; i++) {
			if (!vis[i]) {
				vis[i] = true;
				ans[stop] = (char) (i + '0');
				run(stop + 1);
				vis[i] = false;
				ans[stop] = 0;
			}
		}
	}

	static void Arrayssort(int[] a) {
		int n = a.length;// shuffle, then sort
		for (int i = 0; i < n; i++) {
			int oi = random.nextInt(n);
			int temp = a[oi];
			a[oi] = a[i];
			a[i] = temp;
		}
		java.util.Arrays.sort(a);
	}

	private static class Scanner {
		public BufferedReader reader;
		public StringTokenizer st;

		public Scanner(InputStream file) throws FileNotFoundException {
			reader = new BufferedReader(new InputStreamReader(file));
			st = null;
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String line = reader.readLine();
					if (line == null)
						return null;
					st = new StringTokenizer(line);
				} catch (Exception e) {
					throw (new RuntimeException());
				}
			}
			return st.nextToken();
		}

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

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

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

		public String nextLine() throws IOException {
			return reader.readLine();
		}
	}

}