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 |
