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 s(arr):
    ans = 0
    for i in arr:
        ans+=int(i)
    return ans

def unique_numbe():
    for i in range(int(input())):
        n = int(input())
        ans = '0'
        i = 9
        game = False
        while i>=1:
            sums = s(ans)
            if sums+i <= n:
                ans+=str(i)
            sums = s(ans)
            if sums==n:
                arr = list(ans)
                arr.sort()
                a = ''.join(arr)
                print(a[1:])
                game = True
                break
            i-=1
        if game==False:
            print('-1')
unique_numbe()