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 Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		for(int y=0;y<t;++y)
		{
		    int x=sc.nextInt();
		    if(x>45)
		    {
		        System.out.println(-1);
		        continue;
		    }
		    else{
		        ArrayList<Integer> al=new ArrayList<>();
		        int max=9;
		        while(x>0)
		        {
		            al.add(Math.min(x,max));
		            
		            x=x-max;
		            --max;
		        }
		        for(int i=al.size()-1;i>=0;--i){
		            System.out.print(al.get(i));
		        }
		        System.out.println();
		    }
		}
	}
}