CF1388B.Captain Flint and a Long Voyage

Captain Flint and his crew keep heading to a savage shore of Byteland for several months already, drinking rum and telling stories. In such moments uncle Bogdan often remembers his nephew Denis. Today, he has told a story about how Denis helped him to come up with an interesting problem and asked the crew to solve it.

In the beginning, uncle Bogdan wrote on a board a positive integer $x$ consisting of $n$ digits. After that, he wiped out $x$ and wrote integer $k$ instead, which was the concatenation of binary representations of digits $x$ consists of (without leading zeroes). For example, let $x = 729$, then $k = 111101001$ (since $7 = 111$, $2 = 10$, $9 = 1001$).

After some time, uncle Bogdan understood that he doesn't know what to do with $k$ and asked Denis to help. Denis decided to wipe last $n$ digits of $k$ and named the new number as $r$.

As a result, Denis proposed to find such integer $x$ of length $n$ that $r$ (as number) is maximum possible. If there are multiple valid $x$ then Denis is interested in the minimum one.

All crew members, including captain Flint himself, easily solved the task. All, except cabin boy Kostya, who was too drunk to think straight. But what about you?

Note: in this task, we compare integers ($x$ or $k$) as numbers (despite what representations they are written in), so $729 \lt 1999$ or $111 \lt 1000$.

船长弗林特和他的船员们已经朝着比特兰的野蛮海岸航行数月之久，一边喝着朗姆酒，一边讲故事。在这样的时刻，博格丹大叔常常想起他的侄子德尼斯。今天，他讲了一个故事，讲述了德尼斯如何帮助他构思出一个有趣的问题，并请全体船员来解答它。

一开始，博格丹大叔在黑板上写下一个由 $n$ 位数字组成的正整数 $x$。随后，他擦掉了 $x$，转而写下整数 $k$，该数是 $x$ 的各位数字的二进制表示（不带前导零）按顺序拼接而成的结果。例如，若 $x = 729$，则 $k = 111101001$（因为 $7 = 111$，$2 = 10$，$9 = 1001$）。

过了一段时间，博格丹大叔意识到自己不知该如何处理 $k$，于是请德尼斯帮忙。德尼斯决定将 $k$ 的末尾 $n$ 位数字擦去，并将得到的新数记作 $r$。

最终，德尼斯提出：找出一个长度为 $n$ 的整数 $x$，使得 $r$（作为数值）尽可能大；若存在多个满足条件的 $x$，则取其中最小的一个。

全体船员，包括船长弗林特本人，都轻松地解决了这个问题。所有人，除了水手学徒科斯佳——他醉得太厉害，根本无法清晰思考。那么，你呢？

注意：本题中，我们以数值大小（而非其表示形式）来比较整数（如 $x$ 或 $k$），因此有 $729 \lt 1999$，或 $111 \lt 1000$。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Next $t$ lines contain test cases — one per test case. The one and only line of each test case contains the single integer $n$ ($1 \le n \le 10^5$) — the length of the integer $x$ you need to find.

It's guaranteed that the sum of $n$ from all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

接下来的 $t$ 行为测试用例，每行一个测试用例。每个测试用例仅包含一个整数 $n$（$1 \le n \le 10^5$）—— 即你需要找到的整数 $x$ 的长度。

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

For each test case, print the minimum integer $x$ of length $n$ such that obtained by Denis number $r$ is maximum possible.

对于每个测试用例，输出长度为 $n$ 的最小整数 $x$，使得 Denis 数 $r$ 达到最大可能值。

In the second test case (with $n = 3$), if uncle Bogdan had $x = 998$ then $k = 100110011000$. Denis (by wiping last $n = 3$ digits) will obtain $r = 100110011$.

It can be proved that the $100110011$ is the maximum possible $r$ Denis can obtain and $998$ is the minimum $x$ to obtain it.

在第二个测试用例中（$n = 3$），若伯父 Bogdan 拥有 $x = 998$，则 $k = 100110011000$。Denis（通过擦除末尾 $n = 3$ 位数字）将得到 $r = 100110011$。

可以证明，$100110011$ 是 Denis 能够得到的最大可能的 $r$，而 $998$ 是得到该 $r$ 的最小 $x$。