D. Dr. Agos's Dark Mode
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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.

Example
Input
6
1
2
3
4
5
6
Output
1
11
101
0101
10101
010100
Note

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.