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

Limits: 1s, 512 MB

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 ≤ 1014).

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

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

Discussion