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 sol(x,idx,st):
    global arr
    if x==0:
        arr.append(st)
    elif x>0 and idx<=9:
        sol(x,idx+1,st)
        sol(x-idx, idx+1, st+str(idx))


for _ in range(int(input())):
    x=int(input())
    digits="123456789"
    arr=[]
    sol(x,1,"")
    if not arr:
        print(-1)
    else:
        ans = arr[0]
        for a in arr:
            if len(a)<len(ans):
                ans=a
            elif len(a)==len(ans):
                ans=min(a,ans)
        print(ans)