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 PYTHON):

Solution:
import sys
if len(sys.argv) > 2 and sys.argv[1] == "i.txt" and sys.argv[2] == "o.txt":
    input = open(sys.argv[1], 'r').readline
    sys.stdout = open(sys.argv[2], 'w')
else:
    input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
def instr():
    s = input()
    return s[:len(s) - 1]

def main():
    l = [1,2,3,4,5,6,7,8,9]
    d = dict()
    for i in xrange(1, 2**9):
        bi = bin(i).replace("0b", "").zfill(9)
        bil = list(map(int, bi))
        li = [l[j] for j in xrange(9) if bil[j]]
        v = int(''.join(map(str, li)))
        k = sum(li)
        if k in d.keys():
            if d[k] > v:
                d[k] = v
        else:
            d[k] = v

    for _ in xrange(inp()):
        x = inp()
        if x in d.keys():
            print(d[x])
        else:
            print(-1)

if __name__ == "__main__":
    main()