Kirti has got a special task for you. She will give you $T$ numbers and you have to output their representation in base $-2$, each on a new line.

INPUT

First line contains a number $T$, i.e. number of test cases.

Next $T$ lines contains a integer $N$, $N$ is in decimal format.

OUTPUT

Print $T$ lines, each containing the equivalent representation of $i^{th}$ number in base $-2$.

CONSTRAINTS

$T \leq 10^5$

$|N| \leq 10^9$ i.e absolute value of $N$

Note : This is a golf question. If your program produces all output correctly, then the score you'll get is determined by the number of non-whitespace characters used in your code. The lower the count of characters, higher will be your score.