题目描述

Madoka 终于找到了她电脑的管理员密码。她的父亲是一位著名的数学科普作家，因此密码就是下面这个问题的答案。

找到一个最大的十进制数，这个数不包含数字 $0$，且没有相同的数字连续出现，并且其各位数字之和为 $n$。

Madoka 已经厌倦了解数学题，所以请你帮她解决这个问题！

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来每组测试用例包含一行，一个整数 $n$（$1 \le n \le 1000$），表示所需的各位数字之和。

输出格式

对于每组测试用例，输出你能得到的最大数。

说明/提示

所有各位数字之和为 $2$ 且不含 $0$ 的数只有 $2$ 和 $11$。但 $11$ 有两个连续的 $1$，因此不合法。所以答案是 $2$。

所有各位数字之和为 $3$ 且不含 $0$ 的数有 $111$、$12$、$21$ 和 $3$。$111$ 有两个连续的 $1$，因此不合法。所以最大合法数是 $21$。

所有各位数字之和为 $4$ 且不含 $0$ 的数有 $1111$、$211$、$121$、$112$、$13$、$31$、$22$ 和 $4$。$1111$、$211$、$112$、$22$ 都有连续相同的数字，因此不合法。所以最大合法数是 $121$。

由 ChatGPT 4.1 翻译

样例

5
1
2
3
4
5

1
2
21
121
212