Negative Binary

In positional notation the rightmost place value is $b^0 = 1$, and every step to the left multiplies it by the base $b$ once more, giving $b^1$, $b^2$, and so on. With base $-2$ the place values read $1, -2, 4, -8, 16, -32, \dots$ from right to left. Counting up from 1 therefore goes 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.

Base $-2$ represents a negative number without a separate sign bit. Write a program that prints the decimal number $N$ in base $-2$.

The first line has a positive integer $T$, the number of test cases, with $T \le 100000$.

Each of the next $T$ lines has one integer $N$ with $-10^{17} \le N \le 10^{17}$.

For each test case print one line in the format Case #x: M, where $x$ is the case number starting from 1 and $M$ is the base $-2$ representation of $N$.

$M$ carries no leading zero. When $N = 0$, print 0.