Base -2

The creator of the universe works in mysterious ways. But he 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 (bi), writen right-to-left. Each of which is either 0 or 1 (no negative digits!), and the following equality must hold. n = b0 + b1(−2) + b2(−2)2 + b3(−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.

#11121Base -2

Input

Output