Easy Sequence 2

Dynamic Programming Conte...
Limits 4s, 512 MB

Let’s define a easy sequence F. Where

$F(1) = 1$

$F(2X) = F(X)^2 + 1$

$F(2X+1) = F(X) \times F(X+1) + 2$

Here X is a positive integer. The first few elements of the sequence are 1, 2, 4, 5, 10, 17, 22, 26, 52, and 101.

Now given a value of X, can you compute $F(X)$?

Input

The first line of the input is a positive integer T (T ≤ 100000), the number of test cases. Then T lines follow.

In each line there will be a value of X (1 ≤ X ≤ 1012).

Output

For each case print a line in "Case I: Y" format where I is the test case number and Y is $F(X)$ modulo 264 (or, 18446744073709551616) for the input X.

Sample

InputOutput
10
1
2
3
4
5
6
7
8
9
1000
Case 1: 1
Case 2: 2
Case 3: 4
Case 4: 5
Case 5: 10
Case 6: 17
Case 7: 22
Case 8: 26
Case 9: 52
Case 10: 18047477376854260869