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 PYTHON):

Solution:
from __future__ import division
from sys import stdin, stdout
# from fractions import gcd
# from math import *
# from operator import mul
# from functools import reduce
# from copy import copy
from collections import deque, defaultdict, Counter
from itertools import combinations

rstr = lambda: stdin.readline().strip()
rstrs = lambda: [str(x) for x in stdin.readline().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda: int(stdin.readline())
rints = lambda: [int(x) for x in stdin.readline().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
pr = lambda args, sep: stdout.write(sep.join(map(str, args)) + '\n')
out = []

for _ in range(int(input())):
    x, ans = rint(), float('inf')
    for i in range(1, 11):
        for com in combinations(range(10), i):
            su = sum(com)
            if su == x:
                ans = min(ans, int(''.join(map(str, sorted(com)))))

    print(ans if ans != float('inf') else -1)