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:
import sys
input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))

nTest = inp()

def SumList(Lista2Analyse):
    aux = 0
    for elem in Lista2Analyse:
        aux = aux +elem
    return aux

Vec = list(range(10))
Aux = list()
aux = 45
for i in Vec:
    aux = aux-i
    Aux.append(aux)

def ComputeNCifras(XIn, SumVec,IndexVec):
    for j in SumVec:
        if X <= j:
            return IndexVec[SumVec.index(j)]

Aux.remove(0)
Aux.reverse()
Vec.remove(0)
for i in range(nTest):
    
    Subset = list(range(10))
    Subset.remove(0) 
    X = inp()
    if (X > 0) & (X < 46):
        Ncif = ComputeNCifras(X,Aux,Vec)
        for k in range(1,len(Subset)-Ncif+1):
            Subset.remove(k)
        SumaLastDigits = SumList(Subset[1::])
        Subset[0] = X-SumaLastDigits
        A = list(map(str,Subset))
        print(''.join(A))
    elif X == 0:
        print(0)
    else:
        print(-1)