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 check_distinct(num):
    if len(set(str(num))) == len(list(str(num))):
        return True
    else:
        return False


T = int(input())
for _ in range(T):
    n = int(input())
    m = n
    ls = [i for i in range(1, 10)][::-1]
    lss = [i for i in range(1, 10)]
    ans = ''

    for i in ls:
        if n in lss:
            ans += str(n)
            break
        elif n != 0:
            n -= i
            ans += str(i)
            lss.remove(i)
        else:
            break

    ans = ans[::-1]
    if check_distinct(ans) and sum(map(int, list(ans))) == m:
        print(ans)
    else:
        print(-1)