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:
q={1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 19, 11: 29, 12: 39, 13: 49, 14: 59, 15: 69, 16: 79, 17: 89, 18: 189, 19: 289, 20: 389, 21: 489, 22: 589, 23: 689, 24: 789, 25: 1789, 26: 2789, 27: 3789, 28: 4789, 29: 5789, 30: 6789, 31: 16789, 32: 26789, 33: 36789, 34: 46789, 35: 56789, 36: 156789, 37: 256789, 38: 356789, 39: 456789, 40: 1456789, 41: 2456789, 42: 3456789, 43: 13456789, 44: 23456789, 45: 123456789}
for i in range(int(input())):
    x=int(input())
    if x in q: print(q[x])
    else: print(-1)