题目大意：



经典的汉诺塔

n个盘编号，从小到大 1..n

问：移动的序列中第k步移的是哪个盘

-Input

The first line of the input file is T, the number of test cases.

Each test case contains one integer p (1<=p<10^100).





　

　　　



　

Output

Output the pth element of the sequence in a single line. See the sample for the output format.

Print a blank line between the test cases.









　

　　　



　

Sample Input

Copy to clipboard

4

1

4

100

100000000000000



　

　　　



　

Sample Output

Case 1: 1



Case 2: 3



Case 3: 3



Case 4: 15