Base -2
The creator of the universe works in mysterious ways. Buthe uses a base ten counting system and likes round numbers.
Scott Adams
Everyone knows about base-2 (binary) integers and base-10 (decimal) integers, but what about base "-2"? An integer n written in base "-2" is a sequence of digits (b_i), writen right-to-left. Each of which is either 0 or 1 (no negative digits!), and the following equality must hold.
n = b_0 + b_1(-2) + b_2(-2)^2 + b_3(-2)^3 + ...
The cool thing is that every integer (including the negative ones) has a unique base-"-2" representation, with no minus sign required. Your task is to find this representation.
Input
The first line of input gives the number of cases, n (at most 10000). N test cases follow. Each one is a line containing a decimal integer in the range from -1,000,000,000 to 1,000,000,000.
Output
For each test case, output one line containing "Case #x:" followed by the same integer, written in base "-2" with no leading zeros.