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 os
import sys
#from io import BytesIO, IOBase
#import itertools
import math
#import operator as op
#from functools import cmp_to_key
#import threading
from heapq import heappop, heappush, heapify
#import random
#import bisect
#from queue import PriorityQueue, Queue 
#from collections import defaultdict, deque
#import random
#input = sys.stdin.readline
#def ic(n,a,s=0,st=1): return [a for i in range(s,n,st)]
#def ri(): return int(input())
#def sa(): return map(int,input().split())
#def ra(): return list(map(int,input().split()))
def mati(n): return [intl() for i in range(n)]
iinp = lambda: int(sys.stdin.readline())
inp  = lambda: sys.stdin.readline().strip()
strl = lambda: list(inp().strip().split(" "))
intl = lambda: list(map(int, inp().split(" ")))
mint = lambda: map(int, inp().split())
flol = lambda: list(map(float, inp().split(" ")))
flush = lambda: sys.stdout.flush()
for _ in range(iinp()):
    
    n = iinp()
    if n in range(1,10): 
        print(n)
    elif n>45:
        print(-1)
    elif n==45:
        print(123456789)
    else:
        s='987654321'
        a=[9,17,24,30,35,39,42,44,45]
        for i in range(9):
            if -a[i]+n<0:
                nn=-a[i-1]+n
                if nn:
                    print(str(nn)+s[:i][::-1])
                else:
                    print(s[:i][::-1])
                break