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:
ans={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,
46: -1,
47: -1,
48: -1,
49: -1,
50: -1}

for i in range(int(input())):print(ans[int(input())])