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 sys.subversion[0] == "PyPy":
    import io, atexit
    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))
    
    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()

RS = raw_input
RI = lambda x=int: map(x,RS().split())
RN = lambda x=int: x(RS())
''' ...................................................................... '''
from itertools import combinations

def number(arr):
    val = 0
    for i in arr:
        val = 10*val+i
    return val

num = range(1,10)

comb = []
for i in xrange(1,10):
    comb.extend(combinations(num,i))

for _ in xrange(RN()):
    x = RN()

    ans = float('inf')

    for arr in comb:
        if sum(arr)==x:
            val = number(arr)
            ans = min(ans,val)

    if ans==float('inf'):
        ans=-1

    print ans