CF2264D.Dr. Agos's Dark Mode

Someone has chopped up Dr. Agos's chickens. Furious, he turns to the one thing that still brings him comfort: his OLED screen. Today, he wants almost all of it black.

The screen has a single row of $n$ pixels. Its pattern is represented by a binary string $s$; $s_i = 0$ means that the $i$-th pixel is dark, and $s_i = 1$ means that it is lit.

Dr. Agos finds a contiguous segment of pixels irritating if, when read from left to right as a binary integer, its value is divisible by $3$. More precisely, the segment from position $l$ to position $r$ ($1 \le l \le r \le n$) has value $$ \sum_{i=l}^{r} s_i \cdot 2^{r-i}. $$ Leading zeroes are allowed. A segment consisting only of dark pixels has value $0$, which is also divisible by $3$.

Let $f(s)$ be the number of irritating segments. Segments with different pairs of endpoints $(l,r)$ are counted separately, even if their pixel patterns are identical.

Dr. Agos wants a pattern with at most three lit pixels that minimizes $f(s)$ among all binary strings of length $n$, including strings with more than three ones. Help him construct such a pattern.

We can show that an answer always exists.

有人把阿戈斯博士的鸡给剁了。他怒不可遏，转而投向唯一还能带给他慰藉的东西：他的 OLED 屏幕。今天，他希望屏幕几乎全部变黑。

该屏幕只有一行 $n$ 个像素。其显示图案由一个二进制字符串 $s$ 表示；其中 $s_i = 0$ 表示第 $i$ 个像素为暗色，$s_i = 1$ 表示为亮色。

阿戈斯博士认为一段连续的像素是“令人烦躁的”，当且仅当将其从左到右视作一个二进制整数时，该整数的值能被 $3$ 整除。更准确地说，位置从 $l$ 到 $r$（$1 \le l \le r \le n$）的这段像素所对应的值为

$$\sum_{i=l}^{r} s_i \cdot 2^{r-i}.$$

允许前导零。仅包含暗色像素的段对应值为 $0$，而 $0$ 也能被 $3$ 整除。

令 $f(s)$ 表示“令人烦躁的”子段的数量。具有不同端点对 $(l,r)$ 的子段均被分别计数，即使它们的像素模式完全相同。

阿戈斯博士希望构造一个至多包含三个亮像素的图案，使得 $f(s)$ 在所有长度为 $n$ 的二进制字符串（包括含超过三个 1 的字符串）中达到最小。请帮助他构造这样的图案。

我们可以证明，这样的答案总是存在的。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of pixels in the row.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示该行中像素的数量。

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

For each test case, print a binary string $s$ of length $n$ describing Dr. Agos's screen. It must contain at most three ones and minimize $f(s)$ among all binary strings of length $n$.

If there are multiple solutions, print any of them.

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串 $s$，表示 Dr. Agos 的屏幕。该字符串中最多包含三个 1，且在所有长度为 $n$ 的二进制字符串中使 $f(s)$ 最小。

若存在多个满足条件的解，输出任意一个即可。

For $n=1$, Dr. Agos can light the only pixel, giving $s=\mathtt{1}$. The only segment has value $1$, so it is not irritating and $f(s)=0$.

For $n=2$, he can light both pixels, giving $s=\mathtt{11}$. The whole row has binary value $3$ and is irritating, while each individual pixel has value $1$. Thus, $f(s)=1$. Every binary string of length $2$ has at least one irritating segment, so this is optimal.

The displayed patterns are not necessarily unique.

当 $n=1$ 时，Agos 博士可以点亮唯一的像素，得到 $s=\mathtt{1}$。此时唯一的一段的值为 $1$，因此不令人烦躁，故 $f(s)=0$。

当 $n=2$ 时，他可以点亮两个像素，得到 $s=\mathtt{11}$。整行的二进制值为 $3$，是令人烦躁的；而每个单独的像素的值均为 $1$。因此，$f(s)=1$。所有长度为 $2$ 的二进制字符串均至少含有一段令人烦躁的子段，因此该方案是最优的。

所展示的模式未必唯一。