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:
from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
sys.setrecursionlimit(100000)
if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream
 
 
if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)
 
        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)
 
        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)
 
    input = raw_input
    range = xrange
 
    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip
 
 
def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.
 
    Args:
        sync (bool, optional): The new synchronization setting.
 
    """
    global input, flush
 
    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')
 
        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

def dd():
    return map(int,input().split())    
def arr():
    return list(map(int,input().split()))
def twinSort(X,Y):
    #sorting X wrt Y
    return [x for _,x in sorted(zip(Y,X))]

def solve():
    n=int(input())
    if n<10:
        print(n)
    else:
        # ans=[]
        # ans.append(0)
        # for i in range(n//10):
        #     ans.append(9)
        
        # index=1
        # ans[0]=n-9*(n//10)
        # for i in range(len(ans)-2,-1,-1):
        #     if ans[i]==9:
        #         ans[i]-=index
        #         index+=1
        
        # print(ans)
        use=[i for i in range(1,10)]

        if n>9*(5):
            print(-1)
        else:
            ans=[]
            s=0
            nn=n
            while len(use):
                if nn in use:
                    ans.append(nn)
                    break
                else:
                    nn-=use[-1]
                    ans.append(use[-1])
                    use.pop()
            ans.sort()
            ssss=''
            for i in ans:
                ssss+=str(i)
            print(ssss)

            




def main():
    testCase=1
    if testCase:
        for _ in range(int(input())):
            solve()
    else:
        solve()
    
if __name__ == '__main__':
    sync_with_stdio(False)
    main()