Time Limit: 3000 mSec Memory Limit : 32768 KB

In mathematics, the Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa, known as Fibonacci (a contraction of filius Bonaccio, "son of Bonaccio"). Fibonacci's 1202 book Liber Abaci introduced the sequence to Western European mathematics, although the sequence had been previously described in Indian mathematics.
That is, after two starting values, each number is the sum of the two preceding numbers. The first Fibonacci numbers (sequence A000045 in OEIS), also denoted as F[n];
Then you get a new sequence A(Here a and b are two given integers.).

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc. In mathematical terms, it is defined by the following recurrence relation:

Now we define A[n] as a function with the following expression:

Now we define the sub sequence of A ,that is , B[j,k] = {A[j],A[j+1]…A[j+k-1]} And the number of times it appears in A is defined as Cnt[j,k]

For example, A = {1,1,1,1,1} and B[0][2] = {1,1} so Cnt[0][2] =4 (overlap is allowed)

We define (k>=1), as you see, S[0][2] = (4-1) * 2 = 6 for the example above.

Now your task is simple, just write a program and calculate the max value of S[j][k] for all possible j and k.

In the first line of input, there is one integer T indicates the cases. ( T<=10)

Then T cases are following.

For any case, there is only one single line contains a,b,c,n (1 <= a,b <= 10^9,1 <= c <= 1000,1 <= n <= 200000) n is the total length of sequence A.

You are expected to output one single line.

Print “Case %m: “ at first where m is the case number count from 1.

Then output a integer indicates the max value if S[j][k] for all possible j and k.

2
1 1 10 5
1 1 1 3

Case 1: 0
Case 2: 2

In case 1, the A is:
A[0] = 10
A[1] = 100
A[2] = 10000
A[3] = 198503
A[4] = 49967
A = {10,100,10000,198503,49967}
S[0][1] = S[1][1] = S[2][1] = S[3][1] = S[4][1] = 0
S[0][2] = S[1][2] = S[2][2] = S[3][2] = 0
S[0][3] = S[1][3] = S[2][3] = 0
S[0][4] = S[1][4] = 0
S[0][5] = 0
So the answer is 0.
In case 2, the A is:
A[0] =0
A[1] = 0
A[2] = 0
A = {0,0,0}
S[0][1] = S[1][1] = S[2][1] = 2 * 1 = 2
S[0][2] = S[1][2] = 1 * 2 = 2
S[0][3] = 0
So the answer is 2.