# 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

Let’s define a easy sequence F. Where

**F**(1) = 1**F**(2**X**) = **F**(**X**)^{2} + 1**F**(2**X**+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 **10 ^{12} )**.

#### Output

For each case print a line in “Case I: Y” format where **I** is test case number and **Y** is **F**(**X**) modulo **2 ^{64}** or

**18446744073709551616**for the input

**X**.

#### Samples

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 |

#### ridowan007

→

Login to submit