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:
/* package codechef; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		major:
		for(int z=0;z<t;z++)
		{
		    int n=sc.nextInt();
		    if(n>45)
		    {
		        System.out.println(-1);
		        continue major;
		    }
		    int ans=0,sum=0;
		    for(int i=9;n-sum>0;i--)
		    {
		        ans*=10;
		        if(n-sum<i)
		            ans+=(n-sum);
		        else
		            ans+=i;
		        sum+=i;
		    }
		    int ans2=0;
		    while(ans>0)
		    {
		        ans2*=10;
		        ans2+=ans%10;
		        ans/=10;
		    }
		    System.out.println(ans2);
		}
	}
}