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:
from sys import stdin,stdout
from collections import defaultdict
input=stdin.readline
#print=stdout.write
from random import randint
import math
###-----------Code Begins----------##
import itertools

L= [int(i) for i in range(1,10)]
mylists=[]
for n in range(1,10):
    LL=list(itertools.combinations(L, n))
    for item in LL:
        mylists.append(item)

for i in range(len(mylists)):
    mylists[i] = sorted(list(mylists[i]))
mylists.sort()
d={}
for ttt in range(51):
    x=ttt
    target=[]
    for item in mylists:
        s=0
        for ij in item:
            s+= int(ij)
        if(s==x and len(item)>0):
            target.append(item)
    if(len(target)==0):
        d[x]=-1
        #print("-1")
    else:
        L=len(target[0])
        for item in target:
            L=min(L, len(item))
        final=[]
        for item in target:
            if(len(item)==L):
                final.append(item)
        final.sort()
        k=final[0]
        for i in range(len(k)): 
            k[i]=str(k[i])
        answer= "".join(k)
        d[x]=answer
        #print(str(answer))

for _ in range(int(input())):
    q=int(input())
    print(d[q])