# Practice on Toph

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

## Oh Functions

Let’s define functions f and g as:

f(x) = 2 * ( f(x-1) + g(x-1) - 1 ) * ( f(x-1) + g(x-1) - 3 ) + 12 * f(x-1) - 13

g(x) = ( f(x-1) + g(x-1) ) * ( f(x-1) + g(x-1) - 4 ) + 12 * g(x-1) + 7

And f(0) = 2, g(0) = 1.

Here, x is non-negative integers. For giving a value of x, find the value of f(x) and g(x).

#### Input

First line of the input is **T** **(T ≤ 50000)**, then **T** test cases follows. Each case has only one line containing a positive integer **x** **(1 ≤ x ≤ 10 ^{14})**.

#### Output

For each test case print a line in **Case I: F G** format where **I** is case number and **F** is **f(x)** and **G** is **g(x)**. As **F** and **G** can be very big number, output them with modulo **1,000,000,007**.

#### Samples

Input | Output |
---|---|

4 1 2 3 4 | Case 1: 11 16 Case 2: 1367 820 Case 3: 9564839 4784068 Case 4: 261293629 130666607 |

Nobel_ruetttt Earliest, Jul '17

Nobel_ruetttt Fastest, 173739.8s

Nobel_ruetttt Lightest, 1.7 MB

KnightMare Shortest, 1403B

Login to submit