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 whatever; // 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 Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		 int [] a =  new int [46];
		a[0]=0;
		int k=0,s=1,j=0,i=0,l=1;
		for( i=9;i>0;i--)
		{
			for( j=1;j<=i;j++)
			{
			a[l]=s*j + a[k];
			l++;
			}
			k=l-1;
			s*=10;
	    }
	  
		while(t>0)
		{
			int n =  sc.nextInt();
		   if(n>45)
		   System.out.println("-1");
		   else
		   System.out.println(a[n]);
		   t--;
		}
	}
}