CF1467A.Wizard of Orz

There are $n$ digital panels placed in a straight line. Each panel can show any digit from $0$ to $9$. Initially, all panels show $0$.

Every second, the digit shown by each panel increases by $1$. In other words, at the end of every second, a panel that showed $9$ would now show $0$, a panel that showed $0$ would now show $1$, a panel that showed $1$ would now show $2$, and so on.

When a panel is paused, the digit displayed on the panel does not change in the subsequent seconds.

You must pause exactly one of these panels, at any second you wish. Then, the panels adjacent to it get paused one second later, the panels adjacent to those get paused $2$ seconds later, and so on. In other words, if you pause panel $x$, panel $y$ (for all valid $y$) would be paused exactly $|x−y|$ seconds later.

For example, suppose there are $4$ panels, and the $3$-rd panel is paused when the digit $9$ is on it.

• The panel $1$ pauses $2$ seconds later, so it has the digit $1$;
• the panel $2$ pauses $1$ second later, so it has the digit $0$;
• the panel $4$ pauses $1$ second later, so it has the digit $0$.

The resulting $4$-digit number is $1090$. Note that this example is not optimal for $n = 4$.

Once all panels have been paused, you write the digits displayed on them from left to right, to form an $n$ digit number (it can consist of leading zeros). What is the largest possible number you can get? Initially, all panels show $0$.

有 $n$ 个数字面板排成一条直线。每个面板可以显示 $0$ 到 $9$ 中的任意一个数字。初始时，所有面板均显示 $0$。

每过一秒，每个面板上显示的数字增加 $1$。换句话说，每过一秒后，原本显示 $9$ 的面板将变为 $0$，原本显示 $0$ 的面板将变为 $1$，原本显示 $1$ 的面板将变为 $2$，依此类推。

当某个面板被暂停时，其显示的数字在后续每一秒中将不再变化。

你必须恰好暂停其中一个面板，且可在任意时刻（即任意秒数）执行该操作。随后，与该面板相邻的面板将在 $1$ 秒后被暂停，与这些已被暂停面板相邻的面板将在 $2$ 秒后被暂停，依此类推。换言之，若你暂停的是第 $x$ 个面板，则对所有合法的 $y$，第 $y$ 个面板将在恰好 $|x - y|$ 秒后被暂停。

例如，假设有 $4$ 个面板，且你在第 $3$ 个面板显示数字 $9$ 时将其暂停：

• 第 $1$ 个面板在 $2$ 秒后暂停，因此其显示数字为 $1$；
• 第 $2$ 个面板在 $1$ 秒后暂停，因此其显示数字为 $0$；
• 第 $4$ 个面板在 $1$ 秒后暂停，因此其显示数字为 $0$。

最终得到的 $4$ 位数字是 $1090$。注意：此例对于 $n = 4$ 并非最优解。

当所有面板均被暂停后，你将从左至右依次写下各面板当前显示的数字，构成一个 $n$ 位数字（允许前导零）。你能得到的最大可能数字是多少？初始时，所有面板均显示 $0$。

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Each test case consists of a single line containing a single integer $n$ ($1 \le n \le 2\cdot10^5$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。每个测试用例由一行组成，该行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）。

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

For each test case, print the largest number you can achieve, if you pause one panel optimally.

对于每个测试用例，输出在最优地暂停一个面板的情况下所能达到的最大数字。

In the first test case, it is optimal to pause the first panel when the number $9$ is displayed on it.

In the second test case, it is optimal to pause the second panel when the number $8$ is displayed on it.

在第一个测试用例中，最优策略是在第一个面板显示数字 $9$ 时暂停它。

在第二个测试用例中，最优策略是在第二个面板显示数字 $8$ 时暂停它。