你是一位臭名昭著的博主，在由法国企业家 Du Rove 创立的某款备受争议的即时通讯软件中拥有广泛的频道和群组网络。为了拥有辨识度高的个人风格，你给所有频道都起了与数字相关的名字，包括 itstwofortyfive、four、two seven three two five、twenty five、0x6ABD 以及 signed integer overflow。

你想开设一个新频道，但你已经用完了所有的数字，所以你需要一个新数字。

今天你最喜欢的数字是 $k$，你想选择某个数字 $n$ 作为新频道的名称。

如果 $n$ 满足以下性质，你就会对这个频道名称 $n$ 感到满意：

• 数字 $n$ 能被 $k$ 整除，
• $n$ 的所有数位之和为 $k$。

你已经找到了较小 $k$ 值下的所有频道名称，所以现在你需要一个程序来处理更大的数字。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。接下来是测试用例的描述。

每个测试用例仅包含一行，其中有一个整数 $k$（$1 \le k \le 10^5$）。

所有测试用例中 $k$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $n$（$1 \le n \le 10^{20k}$）。如果存在多个满足条件的答案，输出其中任意一个即可。

样例

输入样例 1

4
1
9
12
90

输出样例 1

1
81
12121212
2732500014450002500040002147483647000

two seven three two five