提示: 欢迎访问OurACM平台。
Problem 1872 A New Sequence Problem

Accept: 44    Submit: 186
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

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.

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:

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];

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

Then you get a new sequence A(Here a and b are two given integers.).

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.

Input

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.

Output

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.

Sample Input

2 1 1 10 5 1 1 1 3

Sample Output

Case 1: 0 Case 2: 2

Hint

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.

Source

AekdyCoin

Submit  Back  Status  Discuss