弗林特船长和他的船员已经连续几个月前往拜特兰的野蛮海岸,一边喝朗姆酒一边讲故事。在这样的时刻,博格丹叔叔常常想起他的侄子丹尼斯。今天,他讲述了丹尼斯如何帮助他提出一个有趣的问题并要求剧组人员解决它的故事。
一开始,博格丹叔叔在黑板上写了一个由$$$n$$$ 数字组成的正整数$$$x$$$。之后,他删除了 $$$x$$$ 并写入整数 $$$k$$$ ,这是数字 $$$x$$$ 的二进制表示形式的串联(不带前导零)。例如,令 $$$x = 729$$$,则 $$$k = 111101001$$$(因为 $$$7 = 111$$$、$$$2 = 10$$$、$$$9 = 1001$$$)。
一段时间后,博格丹叔叔明白他不知道如何处理$$$k$$$,并请求丹尼斯帮忙。 Denis 决定擦除 $$$k$$$ 的最后 $$$n$$$ 数字,并将新数字命名为 $$$r$$$。
因此,Denis 提议找到长度为 $$$n$$$ 的整数 $$$x$$$,使得 $$$r$$$(作为数字)尽可能最大。如果存在多个有效的 $$$x$$$,那么丹尼斯会对最小的一个感兴趣。
所有船员,包括弗林特船长本人,轻松解决了任务。除了机舱男孩克斯特亚(Kostya)之外,其他人都喝醉了,无法正常思考。但你呢?
注意:在此任务中,我们将整数($$$x$$$ 或 $$$k$$$)与数字进行比较(无论它们以何种表示形式写入),因此 $$$729 < 1999$$$ 或 $$$111 < 1000$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
接下来的 $$$t$$$ 行包含测试用例 - 每个测试用例一个。每个测试用例的唯一一行包含单个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 您需要查找的整数 $$$x$$$ 的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印长度为 $$$n$$$ 的最小整数 $$$x$$$,以便通过 Denis 数 $$$r$$$ 获得最大可能。
示例
输入 #1
2 1 3
输出 #1
8 998
注意
在第二个测试用例中($$$n = 3$$$),如果 Bogdan 叔叔的 $$$x = 998$$$ 则 $$$k = 100110011000$$$。 Denis(通过擦除最后 $$$n = 3$$$ 数字)将获得 $$$r = 100110011$$$。
可以证明$$$100110011$$$是Denis所能获得的最大可能的$$$r$$$,$$$998$$$是获得它的最小$$$x$$$。