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 representa- tion, 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. Sample Input 4 1 7 -2 0 Sample Output Case #1: 1 Case #2: 11011 Case #3: 10 Case #4: 0