← 返回题目列表

Codeforces · 1467/A

A. 奥兹巫师

中文机器翻译题面 查看原题

有 $$$n$$$ 数字面板放置在一条直线上。每个面板可以显示从 $$$0$$$ 到 $$$9$$$ 的任何数字。最初,所有面板均显示 $$$0$$$。

每秒,每个面板显示的数字都会增加$$$1$$$。换句话说,在每一秒结束时,显示 $$$9$$$ 的面板现在将显示 $$$0$$$,显示 $$$0$$$ 的面板现在将显示 $$$1$$$,显示 $$$1$$$ 的面板现在将显示 $$$2$$$,依此类推。

当面板暂停时,面板上显示的数字在接下来的几秒内不会改变。

您必须根据需要随时暂停其中一个面板。然后,与其相邻的面板在一秒后暂停,与其相邻的面板在 $$$2$$$ 秒后暂停,依此类推。换句话说,如果您暂停面板 $$$x$$$,则面板 $$$y$$$(对于所有有效的 $$$y$$$)将在 $$$|x−y|$$$ 秒后暂停。

例如,假设有 $$$4$$$ 面板,当 $$$3$$$-rd 面板上出现数字 $$$9$$$ 时,该面板暂停。

- 面板$$$1$$$在$$$2$$$秒后暂停,因此它有数字$$$1$$$;
- 面板 $$$2$$$ 稍后暂停 $$$1$$$,因此它具有数字 $$$0$$$;
- 面板 $$$4$$$ 稍后暂停 $$$1$$$,因此它具有数字 $$$0$$$。

生成的 $$$4$$$ 位数字是 $$$1090$$$。请注意,此示例对于 $$$n = 4$$$ 而言并非最佳。

一旦所有面板都暂停,您可以从左到右写入面板上显示的数字,以形成 $$$n$$$ 数字(可以包含前导零)。你能得到的最大数字是多少?最初,所有面板均显示 $$$0$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。每个测试用例由一行组成,其中包含单个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,如果以最佳方式暂停一个面板,则打印可以达到的最大数字。

示例

输入 #1

2
1
2

输出 #1

9
98

注意

在第一个测试用例中,最好在第一个面板上显示数字 $$$9$$$ 时暂停该面板。

在第二个测试用例中,当数字 $$$8$$$ 显示在第二个面板上时,最好暂停第二个面板。