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.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;
import java.util.Vector;
import java.util.Scanner;

public class ahh {

	static Scanner scn = new Scanner(System.in);

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int t = scn.nextInt();
		while (t-- > 0)
		{
			//prob1();
			//prob2();
			prob3();
			//prob4();
		}
	}
	public static void prob1()
	{
		int n = scn.nextInt();
		int arr[] = new int[n], brr[] = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = scn.nextInt();
		int j = 1, k = 0;
		if (n % 2 == 0) 
		{
			for (int i = 0; i < n / 2; i++) {
				brr[k] = arr[i];
				k += 2;
			}
			for (int i = n - 1; i >= n / 2; i--) {
				brr[j] = arr[i];
				j += 2;
			}
		}
		else
		{
			for (int i = 0; i <= n / 2; i++) {
				brr[k] = arr[i];
				k += 2;
			}
			for (int i = n - 1; i > n / 2; i--) {
				brr[j] = arr[i];
				j += 2;
			}
			
		}
		for (int i = 0; i < n; i++)
			System.out.print(brr[i] + " ");
		System.out.println();

	}
	public static void prob2()

	{	int n=scn.nextInt();
		String str=scn.next();
		if(str.charAt(0)=='2'&&str.charAt(n-1)!='0')
		{
			if(str.substring(0, 4).equals("2020"))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
		else if(str.charAt(0)!='2'&&str.charAt(n-1)=='0')
		{
			if(str.substring(n-4, n).equals("2020"))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
		else if(str.charAt(0)=='2'&&str.charAt(n-1)=='0')
		{
			if(str.substring(0, 1).equals("2")&&str.substring(n-3).equals("020")||str.substring(0, 2).equals("20")&&str.substring(n-2).equals("20")||str.substring(0,3).equals("202")&&str.substring(n-1).equals("0"))
				System.out.println("YES");
			else
				System.out.println("NO");
				
		}
		else
			System.out.println("NO");
		
		
	}
	
	public static void prob3()
	{
		int n=scn.nextInt();
		if(n>45)
			System.out.println("-1");
		else if(n<10)
		{
			System.out.println(n);
		}
		else
		{
			if(n==10)
				System.out.println("19");
			else if(n==11)
				System.out.println("29");
			else if(n==12)
				System.out.println("39");
			else if(n==13)
				System.out.println("49");
			else if(n==14)
				System.out.println("59");
			else if(n==15)
				System.out.println("69");
			else if(n==16)
				System.out.println("79");
			else if(n==17)
				System.out.println("89");
			else if(n==18)
				System.out.println("189");
			else if(n==19)
				System.out.println("289");
			else if(n==20)
				System.out.println("389");
			else if(n==21)
				System.out.println("489");
			else if(n==22)
				System.out.println("589");
			else if(n==23)
				System.out.println("689");
			else if(n==24)
				System.out.println("789");
			else if(n==25)
				System.out.println("1789");
			else if(n==26)
				System.out.println("2789");
			else if(n==27)
				System.out.println("3789");
			else if(n==28)
				System.out.println("4789");
			else if(n==29)
				System.out.println("5789");
			else if(n==30)
				System.out.println("6789");
			else if(n==31)
				System.out.println("16789");
			else if(n==32)
				System.out.println("26789");
			else if(n==33)
				System.out.println("36789");
			else if(n==34)
				System.out.println("46789");
			else if(n==35)
				System.out.println("56789");
			else if(n==36)
				System.out.println("156789");
			else if(n==37)
				System.out.println("256789");
			else if(n==38)
				System.out.println("356789");
			else if(n==39)
				System.out.println("456789");
			else if(n==40)
				System.out.println("1456789");
			else if(n==41)
				System.out.println("2456789");
			else if(n==42)
				System.out.println("3456789");
			else if(n==43)
				System.out.println("13456789");
			else if(n==44)
				System.out.println("23456789");
			else if(n==45)
				System.out.println("123456789");
		}
	}

	public static void prob4()
	{
		int n=scn.nextInt();
		int arr[]=new int[n],sum=0;
		for(int i=0;i<n;i++)
		{
			arr[i]=scn.nextInt();
			sum+=arr[i];
		}
		for(int i=0;i<n;i++)
		{
			if(fun(i, arr, sum))
			{
				System.out.println(i);
				return;
			}
		}
		
	}
	public static boolean fun(int i,int arr[],int sum)
	{		i=arr.length-i;
		int count=0,val=sum/i;
		
		if(sum%i!=0)
			return false;
		else
		{	//System.out.println(i);
			for(int j=0;j<arr.length;j++)
			{
				count+=arr[j];
				if(count==val)
				{
					count=0;
				}
				if(count>val)
					return false;
			}
			return true;
		}
	}
	public static int coin(int arr[], int i, int j, int count, int sumb) {
		if (count == arr.length / 2)
			return 0;
		if (i == arr.length || j == 0)
			return 0;

		int a = 0, b = 0, c = 0, d = 0;
		a = coin(arr, i + 1, j, count + 1, sumb) + arr[i];
		b = coin(arr, i + 1, j, count + 1, sumb + arr[i]);
		c = coin(arr, i, j - 1, count + 1, sumb) + arr[j];
		d = coin(arr, i, j - 1, count + 1, sumb + arr[j]);
		return Math.max(a, Math.max(b, Math.max(c, d)));
	}

	public static long gcd(long a, long b) {
		while (b > 0) {
			long c = a % b;
			a = b;
			b = c;
		}
		return a;
	}

}

class pair {
	int x, y;

	pair(int a, int b) {
		this.x = a;
		this.y = b;
	}

	public int hashCode() {
		return x * 31 + y * 31;
	}

	public boolean equals(Object other) {
		if (this == other)
			return true;

		if (other instanceof pair) {
			pair pt = (pair) other;

			return pt.x == this.x && pt.y == this.y;
		} else
			return false;
	}

}

class sort implements Comparator<pair> {

	@Override
	public int compare(pair o1, pair o2) {
		// TODO Auto-generated method stub
		int a = o1.x - o2.x;

		return 0;
	}

}