Background

Special for beginners, ^_^

Description

徐老师在黑板上贴出一张如下的“洞数表"并留下了一道题目：

给你一个正整数 $k$，请你构造值最小的正整数（不能有前导 $0$），使得它所有数位的洞数之和恰好为 $k$。

Format

Input

• 第一行输入一个整数 $T \leq 10 ^ 3$，表示测试组数。
• 接下来 $T$ 行，每行一个正整数 $k \leq 10^5$，表示希望的洞数总和。

Output

对于每组数据，输出一个没有前导 $0$、且所有数位洞数之和等于 $k$ 的最小正整数。

Samples

2
1
2

4
8

Limitation

1s, 1024KiB for each test case.