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:
import java.io.*;
import java.util.StringTokenizer;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class TaskC {
    static Reader rd=new Reader() ;
    static PrintWriter out=new PrintWriter(System.out) ;

    static class Reader
    {
        StringTokenizer stringTokenizer;
        BufferedReader bufferedReader;

        public Reader()
        {
            bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        }

        String next()
        {
            while (stringTokenizer == null || !stringTokenizer.hasMoreElements())
            {
                try
                {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                }
                catch (Exception e){}
            }
            return stringTokenizer.nextToken();
        }

        int ni()
        {
            return Integer.parseInt(next());
        }
    }

    static void solve(int T) throws IOException {
        while(T-->0){
			int x=rd.ni() ;
			long ans=-1;
			if(x<=9) ans=x;
			else
				if(x<=17) ans=(x-9)*10+9 ;
				else 
					if(x<=24) ans=(x-17)*100+89 ;
					else 
						if(x<=30) ans=(x-24)*1000+789 ;
						else 
							if(x<=35) ans=(x-30)*10000+6789 ;
							else 
								if(x<=39) ans=(x-35)*100000+56789;
								else 
									if(x<=42) ans=(x-39)*1000000+456789 ;
									else 
										if(x<=44) ans=(x-42)*10000000+3456789 ;
										else 
											if(x==45) ans=123456789 ;
											else ans=-1;
		
		out.println(ans) ;
		}

    }

    public static void main(String args[]) throws IOException {
        solve(rd.ni());
        out.flush();
    }
}