Number bases have place values that start at 1 (base to the 0 power) and proceed right-to-left to base-1, base-2, and so on. In base-2, the place values are 1, -2, 4, -8, 16, -32, ... (reading from right to left). Thus, counting increasingly from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on. The advantage of base-2 representation is that you do not have to maintain a sign bit. Your task is to print the given decimal number in base-2. 

입력 형식

The first line has a positive integer T, T <= 100000, denoting the number of test cases. This is followed by each test case per line. </p>

Each test case contains a single integer decimal number N between -10¹⁷ to 10¹⁷ inclusive. 

출력 형식

For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the base-2 representation of the given decimal number. 

예제 입력

15
1
-1
2
10
0
100
-100
50
60
1000
-10000
50000
-25000
12345
-23456

예제 출력

Case #1: 1
Case #2: 11
Case #3: 110
Case #4: 11110
Case #5: 0
Case #6: 110100100
Case #7: 11101100
Case #8: 1110110
Case #9: 1001100
Case #10: 10000111000
Case #11: 10100100110000
Case #12: 11100011101010000
Case #13: 1110001110101000
Case #14: 111000001001001
Case #15: 1110010110100000