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.util.*;

public class Codeforces {

    static int highestPowerof2(int n)
    {
        int p = (int)(Math.log(n) /
                Math.log(2));
        return (int)Math.pow(2, p);
    }
    public static int binsearch(long[] a,long x){
        int l = 0;
        int r = a.length;
        while (l <= r){
            int mid = l + (r-l)/2;
            if (a[mid]==x)
                return 1;
            else if (a[mid] < x)
                l = mid+1;
            else
                r = mid-1;
        }
        return 0;
    }
    public static int upperbound(long[] arr,long key){
        int start=0;int end=arr.length-1;
        int idx=-1;
        int mid;
        while(start<=end){
            int i=(start+end)/2;
            if(arr[i]<key){
                start=i+1;
            }
            else if(arr[i]>key){
                end=i-1;
            }
            else{
                idx=i;
                start=i+1;
            }
        }

        return idx;    }
    public static int lowerbound(long[] arr,long key){
        int start=0;int end=arr.length-1;
        int idx=-1;
        int mid;
        while(start<=end){
            int i=(start+end)/2;
            if(arr[i]<key){
                start=i+1;
            }
            else if(arr[i]>key){
                end=i-1;
            }
            else{
                idx=i;
                end=i-1;
            }
        }
        return idx;
    }
    public static int searchInsert(long[] nums, long target) {
        int s=0,e=nums.length-1;
        int mid;
        if(target<nums[0]){
            return 0;
        }
        while(s<=e){
            mid=(s+e)/2;
            if(nums[mid]>target){
                e=mid-1;
            }
            else if(nums[mid]==target){
                return mid;
            }
            else{
                s=mid+1;
            }
        }
        return s;
    }
    public static class Pair{
        int a,b;
        Pair(int a,int b){
            this.a = a;
            this.b = b;
        }
    }
    static boolean isPrime(long n)
    {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;

        if (n % 2 == 0 || n % 3 == 0)
            return false;

        for (long i = 5; i <= Math.sqrt(n); i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }
    public static long fastExpo(long a,int n,int mod){
        if (n == 0)
            return 1;
        else{
            if ((n&1) == 1){
                long x = fastExpo(a,n/2,mod);
                return (((a*x)%mod)*x)%mod;
            }
            else{
                long x = fastExpo(a,n/2,mod);
                return (((x%mod)*(x%mod))%mod)%mod;
            }
        }
    }
    public static long modInverse(long n,int p){
        return fastExpo(n,p-2,p);
    }
    public static long nCr(int n,int r,long[] fact,int mod){
        long val =  (((fact[n] * modInverse(fact[r],mod))%mod)*modInverse(fact[n-r],mod))%mod;
        return val;
    }
    public static void factorial(long[] fact,int n,int mod){
        for (int i=1;i<=n;i++){
            fact[i] = (fact[i-1] * i)%mod;
        }
    }
    public static boolean isExcellent(int a,int b,int x){
        while (x != 0){
            int digit = x%10;
            if (digit != a && digit != b)
                return false;
            x /= 10;
        }
        return true;
    }
    public static void subSets(int[] a,int n,ArrayList<Integer> subset,ArrayList<ArrayList<Integer>> subsets){
        if (n == 0){
            subsets.add(subset);
            return;
        }
        subset.add(a[n-1]);
        subSets(a,n-1,subset,subsets);
        subset.remove(subset.size() - 1);
        subSets(a,n-1,subset,subsets);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
           int n = sc.nextInt();
           String ans = "";
           if (n > 45){
               System.out.println(-1);
               continue;
           }
           if (n < 10){
               System.out.println(n);
               continue;
           }
           if (n <= 17){
               ans = String.valueOf(n-9) + "9";
           }
           else if (n <= 24){
               ans = String.valueOf(n-8-9) + "89";
           }
           else if (n <= 30){
               ans = String.valueOf(n-9-8-7) + "789";
           }
           else if (n <= 35){
               ans = String.valueOf(n-9-8-7-6) + "6789";
           }
           else if (n <= 39){
               ans = String.valueOf(n-9-8-7-6-5) + "56789";
           }
           else if (n <= 42){
               ans = String.valueOf(n-9-8-7-6-5-4) + "456789";
           }
           else if (n <= 44){
               ans = String.valueOf(n-9-8-7-6-5-4-3) + "3456789";
           }
           else{
               ans = "123456789";
           }
            System.out.println(ans);
        }
    }
}