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:
# -*- coding: utf-8 -*-
"""
Created on Tue Dec 22 15:53:37 2020

@author: SJK
"""

for _ in range(int(input())):
    x=int(input())
    c,i,ans,n=0,9,0,x
    for i in range(9,0,-1):
        if (n-i)<=0:
            break
        ans+=i*(10**c)
        c+=1
        n=n-i
        
    if n>0 and x<46:
        ans+=(n)*(10**c)
        print(ans)
    
    else:
        print(-1)