Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Sequence 2

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) * F(X+1) + 2

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

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 <= 1000000000000 or 1012 ).

Output

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

Samples

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

Author
Discussion