Problem E
Shortlex

Image by Sarah Grillo (Axion), Used with permission

The set of all binary strings of finite length, denoted $\{ 0,1\} ^*$, plays an important role in computer science, and it is often useful to impose an ordering on the elements of this set. One option is standard lexicographic order (dictionary order with the convention that $0$ comes before $1$), but this has a serious drawback: every string that starts with $0$ appears before every string that starts with $1$, and since there are infinitely many strings that start with $0$, it is impossible to assign a finite index to any string that starts with $1$. A better option is length-lexicographic order, also known as shortlex order, which is based on two simple rules. For $x, y \in \{ 0,1\} ^*$:

1. if the length of $x$ is less than the length of $y$, then $x$ precedes $y$

2. if $x$ and $y$ have the same length, then they are ordered lexicographically relative to each other

Following the convention that the empty string (denoted $\varepsilon $) is assigned index $0$, Figure $1$ gives the first $8$ elements and their associated indices in the shortlex order of $\{ 0,1\} ^*$.

Your challenge: For $i \geq 1$, determine the binary string with index $i$ in the shortlex order of $\{ 0,1\} ^*$.

Input

The first line of input contains an integer, $T$ ($1 \leq T \leq 100$), the number of test cases. This is followed by $T$ lines, one per test case. Each test case consists of a single integer, $i$ ($1 \leq i \leq 10^{18}$).

Output

For each test case, $i$, output a single line containing the binary string with index $i$ in the shortlex order of $\{ 0,1\} ^*$.

4
5
10
38
99

10
011
00111
100100