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 unique_number():
    for _ in range(int(input())):
        n = int(input())

        found = False
        ans = []
        i = 0
        k = [9, 8, 7, 6, 5, 4, 3, 2, 1]
        while n != 0 and i < len(k):
            if k[i] <= n:
                if k[i] == n:
                    found = True
                n = n - k[i]
                ans += [k[i]]
            i += 1

        ans.reverse()
        print(*ans if found else [-1], sep='')


if __name__ == "__main__":
    unique_number()