A common example of recursion goes something like this:

long long recur(int x){
if (x==0){
return X0;
}
else if (x==1){
return X1;
}
else{
long long t1=recur(--x);
long long t2=recur(--x);
return t1+t2;
}
}

It is of course easy to calculate the value of this function for any x when the values of X0 and X1 are known. However, your task is to find the value of recur for a given number without being given the values of X0 and X1. Instead, you are given the values of recur(a) and recur(b) for given values of a and b.

Input

Input consists of several cases. The first line contains a single integer N, the number of test cases. N lines follow. Each line contains five integers, a,A,b,B and c, separated by spaces. A is the value of recur(a) and B is the value of recur(b). You can assume that 0 ≤ a,b,c ≤ 50, a != b, and -1018 ≤ A,B ≤ 1018. Also, the value of recur(c), which you have to find, will always be such that -1018 ≤ recur(c) ≤ 1018.

There are at most 200 test cases.

Output

Output should consist of exactly N lines, one for each test case. Each line should be of the format Case #X: Y (without the quotes), where X is the test case and Y is the value of recur(c). See sample output for details.

Sample

Input

Output

4
0 0 1 1 40
0 -5 1 100 6
6 8 11 89 8
0 8 1 -5 50

Case #1: 102334155
Case #2: 775
Case #3: 21
Case #4: -701408733