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:
t=int(input())
for _ in range(t):
    x=int(input())
    b=""
    k=0
    f=0
    if x>=1 and x<10:
        print(x)
    elif x>=10 and x<18:
        k=x-9
        b+=str(k)
        b+="9"
    elif x>=18 and x<25:
        k=x-17
        b+=str(k)
        b+="89"
    elif x>=25 and x<31:
        k=x-24
        b+=str(k)
        b+="789"
    elif x>=31 and x<36:
        k=x-30
        b+=str(k)
        b+="6789"
    elif x>=36 and x<40:
        k=x-35
        b+=str(k)
        b+="56789"
    elif x>=40 and x<43:
        k=x-39
        b+=str(k)
        b+="456789"
    elif x>=43 and x<45:
        k=x-42
        b+=str(k)
        b+="3456789"
    elif x==45:
        b+="123456789"
    else:
        f=1
    if f==0:
        print(b)
    else:
        print("-1")