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) $
?
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).
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.
Input | Output |
---|---|
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 |