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 PYTHON3):

Solution:
# cook your dish here
from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict
from collections import Counter
from bisect import bisect_left
import sys
from queue import PriorityQueue
import operator as op
from functools import reduce
import re

mod = 1000000007

input = sys.stdin.readline
def L():
    return list(map(int, stdin.readline().split()))


def In():
    return map(int, stdin.readline().split())


def I():
    return int(stdin.readline())


def printIn(ob):
    return stdout.write(str(ob) + '\n')


def powerLL(n, p):
    result = 1
    while (p):
        if (p & 1):
            result = result * n % mod
        p = int(p / 2)
        n = n * n % mod
    return result

def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(op.mul, range(n, n - r, -1), 1)
    denom = reduce(op.mul, range(1, r + 1), 1)
    return numer // denom
def SieveOfEratosthenes(n): 
      
    # Create a boolean array "prime[0..n]" and initialize 
    #  all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime_list = []
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
            prime_list.append(p)
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    return prime_list
def get_divisors(n):
    for i in range(1, int(n / 2) + 1):
        if n % i == 0:
            yield i
    yield n


# -------------------------------------

def myCode():
    n = I()
    if n<=9:
        print(n)
    elif n>=10 and n<=17:
        for i in ("12345678"):
            if int(i)+9 == n:
                print(i+str(9))
                break
    elif n>=18 and n<=24:
        for i in ("1234567"):
            if int(i)+8+9 == n:
                print(i+str(89))
                break
    elif n>=25 and n<=30:
        for i in ("123456"):
            if int(i)+7+8+9 == n:
                print(i+str(789))
                break
    elif n>=31 and n<=35:
        for i in ("12345"):
            if int(i)+6+7+8+9 == n:
                print(i+str(6789))
                break
    elif n>=36 and n<=39:
        for i in ("1234"):
            if int(i)+5+6+7+8+9 == n:
                print(i+str(56789))
                break
    elif n>=40 and n<=42:
        for i in ("123"):
            if int(i)+4+5+6+7+8+9 == n:
                print(i+str(456789))
                break
    elif n>=43 and n<=44:
        for i in ("12"):
            if int(i)+3+4+5+6+7+8+9 == n:
                print(i+str(3456789))
                break
    elif n==45:
        print(123456789)
    else:
        print(-1)


    

def main():
    for t in range(I()):
        myCode()
    
if __name__ == '__main__':
    # print(int(math.log2(10)))
    main()