CF 1714B - Remove Prefix

Find the minimum number with the given sum of digits s such that all digits in it are distinct (i.e. all digits are unique).

For example, if s=20, then the answer is 389. This is the minimum number in which all digits are different and the sum of the digits is 20 (3+8+9=20).

For the given s print the required number.

Input

The first line contains an integer t (1≤t≤45) — the number of test cases.

Each test case is specified by a line that contains the only integer s

 (1≤s≤45).

Output

Print t integers — the answers to the given test cases.

------------------------------------------------------------------

找到具有给定数字总和 s 的最小数字，使得其中的所有数字都不同（即所有数字都是唯一的）。

例如，如果s=20，则答案为389。这是所有数字都不同且数字之和为20（3+8+9=20）的最小数字。

对于给定的 s，打印所需的数字。

输入

第一行包含一个整数 t (1≤t≤45) — 测试用例的数量。

每个测试用例由包含唯一整数 s 的行指定

  (1≤s≤45)。

输出

打印 t 个整数 — 给定测试用例的答案。

-------------------

配合数组进行处理要方便些，下面是代码：