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 //do not write package name here */

import java.io.*;
import java.util.*;
public class S {
	public static void main (String[] args) {
		Scanner in=new Scanner(System.in);
		int t=in.nextInt();
		while(t--!=0)
		{
		    int v[]=new int[10];
		    int n=in.nextInt();
		    String s="";
		    int x=9;
		    while(n>=10)
		    {
		        s=x+""+s;
		        v[x]=1;
		        n-=x;
		        x--;
		    }
		    if(n!=0)
		    {
		        if(v[n]==0)
		        {
		            s=n+""+s;
		            n=0;
		        }      
		        else
		        {
		            int z=1;
    		        while(v[z]==0 && n!=0 && z<n)
    		        {
    		            if(v[n-z]==0 && n-z!=z)
    		            {
    		                s=z+""+(n-z)+""+s;
    		                n=0;
    		            }
    		            z++;
    		        }
    		        if(n!=0)
    		        {
    		            x=n-1;
    		            while(x>1)
    		            {
    		                int k=x-1;
    		                if(x>0 && k>0 && n-(x+k)>0 && v[x]==0 && v[k]==0 && v[n-(x+k)]==0 && (n-(x+k)!=x) && (n-(x+k)!=k))
    		                {
    		                    s=(n-(x+k))+""+k+""+x+s;
    		                    n=0;
    		                    break;
    		                }
    		                x--;
    		            }
    		        }
		        }
		        if(n==0)System.out.println(s);
		        else System.out.println(-1);
		    }
		    else System.out.println(s);
		}
	}
}