Statement

For an arbitrary binary string $t$ $^{\text{∗}}$ , let $f(t)$ be the number of non-empty subsequences $^{\text{†}}$ of $t$ that contain only $\mathtt{0}$ , and let $g(t)$ be the number of non-empty subsequences of $t$ that contain at least one $\mathtt{1}$ .

Note that for $f(t)$ and for $g(t)$ , each subsequence is counted as many times as it appears in $t$ . E.g., $f(\mathtt{000}) = 7, g(\mathtt{100}) = 4$ .

We define the oneness of the binary string $t$ to be $|f(t)-g(t)|$ , where for an arbitrary integer $z$ , $|z|$ represents the absolute value of $z$ .

You are given a positive integer $n$ . Find a binary string $s$ of length $n$ such that its oneness is as small as possible. If there are multiple strings, you can print any of them.

$^{\text{∗}}$ A binary string is a string that only consists of characters $\texttt{0}$ and $\texttt{1}$ .

$^{\text{†}}$ A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements. For example, subsequences of $\mathtt{1011101}$ are $\mathtt{0}$ , $\mathtt{1}$ , $\mathtt{11111}$ , $\mathtt{0111}$ , but not $\mathtt{000}$ nor $\mathtt{11100}$ .

Format

Input

The first line contains an integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases.

The only line of each test case contains an integer $n$ ( $1 \leq n \leq 2\cdot10^5$ ) — the length of $s$ .

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

Output

For each test case, output $s$ on a new line. If multiple answers exist, output any.

Sample

3
1
2
3

0
01
010