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.

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.