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.