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.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		while(n--!=0) {
			int a=sc.nextInt();
			int b=0;
			if(a<10) {
				System.out.println(a);
				continue;
			}
			if(a<18) {
				b=9;
				b+=10*(a-9);
				System.out.println(b);
				continue;
			}
			if(a<25) {
				b=89;
				b+=100*(a-17);
				System.out.println(b);
				continue;
			}
			if(a<31) {
				b=789;
				b+=1000*(a-24);
				System.out.println(b);
				continue;
			}
			if(a<36) {
				b=6789;
				b+=10000*(a-30);
				System.out.println(b);
				continue;
			}
			if(a<40) {
				b=56789;
				b+=100000*(a-35);
				System.out.println(b);
				continue;
			}
			if(a<43) {
				b=456789;
				b+=1000000*(a-39);
				System.out.println(b);
				continue;
			}
			if(a<45) {
				b=3456789;
				b+=10000000*(a-42);
				System.out.println(b);
				continue;
			}
			if(a<46) {
				b=23456789;
				b+=100000000*(a-44);
				System.out.println(b);
				continue;
			}
			System.out.println(-1);
		}
	}
}