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 C
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner (System.in);
		int t;
		t=sc.nextInt();
		while(t-->0)
		{
		    int n,x;
		    n=sc.nextInt();
		    x=n;
		    if(n>45)
		    {
		        System.out.println("-1");
		    }
		    else
		    {
		        int cnt=-1,ans=0;
		       for(int i=9;i>0;i--)
		       {
		           if(x>i)
		           {
		               ans=ans+(i*(int)Math.pow(10,++cnt));
		               x=x-i;
		           }
		           else{
		               if(x!=0 &&  x>0)
		               {
		                   ans=ans+(x*(int)Math.pow(10,++cnt));
		               }
		               break;
		           } 
		       }System.out.println(ans);
		    }
		}
		
	}
}