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:
def solve(n):
    if len(n) == 1:
        return [int(n)]
    n = int(n)
    num = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    result = []
    dec = {}
    i = 0
    while i<9:
        if n > num[i] and num[i] not in dec:
            result.append(num[i])
            dec[num[i]] = 1
            n -= num[i]
            i += 1
        elif n <= num[i]:
            if n not in dec:
                result.append(n)
                return sorted(result)
            return -1
        else:
            for j in range(1, n):
                if j != n-j and j not in dec and n-j not in dec:
                    result.append(j)
                    result.append(n-j)
                    return sorted(result)
            return -1
            
    return -1
            
            
    

for _ in range(int(input())):
    n = input()
    p = solve(n)
    if p == -1:
        print(-1)
        
    else:
        t = ""
        for i in p:
            t += str(i)
        print(t)