题目描述

有 $n$ 个数字面板排成一行。每个面板可以显示 $0$ 到 $9$ 之间的任意数字。最初，所有面板都显示 $0$。

每过一秒，每个面板上显示的数字都会加 $1$。也就是说，每秒结束时，显示 $9$ 的面板会变为 $0$，显示 $0$ 的面板会变为 $1$，显示 $1$ 的面板会变为 $2$，以此类推。

当某个面板被暂停后，该面板在接下来的每一秒中显示的数字都不会再发生变化。

你必须在任意时刻暂停恰好一个面板。然后，与其相邻的面板会在 $1$ 秒后被暂停，再相邻的面板会在 $2$ 秒后被暂停，依此类推。换句话说，如果你在第 $x$ 个面板暂停，任意第 $y$ 个面板会在恰好 $|x-y|$ 秒后被暂停。

例如，假设有 $4$ 个面板，在第 $3$ 个面板显示 $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$。

输出格式

对于每个测试用例，输出你能获得的最大数字。

说明/提示

在第一个测试用例中，最优做法是在第一个面板显示 $9$ 时暂停。

在第二个测试用例中，最优做法是在第二个面板显示 $8$ 时暂停。

由 ChatGPT 4.1 翻译

样例

2
1
2

9
98