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:
def ass(a, b):
	if a != b: print(f"Assertion error: {a} != {b}")
	else: print('OK')
def intline(): return [int(item) for item in input().split()]
def line(): return [item for item in input().split()]
def number(): return int(input())
def dump(lst):
	for i, item in enumerate(lst): print(i, item)
def binsearch(arr, a, b):
	m = (a + b) // 2
	if a >= b: return a - 1 if arr[a] == 0 else a
	return binsearch(arr, a, m - 1) if arr[m] == 0 else binsearch(arr, m + 1, b)

arr = [-1]
s = ''
for i in range(10):
	for j in range(1,10-i):
		arr.append(str(j)+s)
	s = str(9-i) + s
for i in range(46,51): arr.append(-1)

for i in range(number()): print(arr[number()])