# Base i-1

Everyone knows about base-2 (binary) integers and base-10 (decimal) integers, but what about base i−1? A complex integer n has the form n = a+bi, where a and b are integers, and i is the square root of −1 (which means that i2 = −1). A complex integer n written in base (i − 1) is a sequence of digits (bi), writen right-to-left, each of which is either 0 or 1 (no negative or imaginary digits!), and the following equality must hold. n=b0 +b1(i−1)+b2(i−1)2 +b3(i−1)3 +... The cool thing is that every complex integer has a unique base-(i-1) 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 20000). N test cases follow. Each one is a line containing a complex integer a + bi as a pair of integers, a and b. Both a and b will be in the range from -1,000,000 to 1,000,000. Output For each test case, output one line containing ‘Case #x:’ followed by the same complex integer, written in base i − 1 with no leading zeros. Sample Input 4 10 23 11 0 00 Sample Output Case #1: 1 Case #2: 1011 Case #3: 111001101 Case #4: 0 A complex system that works is invariably found to have evolved from a simple system that works. John Gaule