Problem F

Base i-1
Input: Standard Input

Output: Standard Output

 

 

A complex system that works is invariably found
to have evolved from a simple system that works.

John Gaule

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 and 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                             Output for Sample Input

4
1 0
2 3
11 0
0 0
 
Case #1: 1
Case #2: 1011
Case #3: 111001101

Case #4: 0

Problem setter: Igor Naverniouk

Special Thanks: Shahriar Manzoor