## Algorithm

A. Frog Jumping
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A frog is currently at the point 00 on a coordinate axis Ox��. It jumps by the following algorithm: the first jump is a units to the right, the second jump is b units to the left, the third jump is a units to the right, the fourth jump is b units to the left, and so on.

Formally:

• if the frog has jumped an even number of times (before the current jump), it jumps from its current position x to position x+a�+�;
• otherwise it jumps from its current position x to position xb�−�.

Your task is to calculate the position of the frog after k jumps.

But... One more thing. You are watching t different frogs so you have to answer t independent queries.

Input

The first line of the input contains one integer t (1t10001≤�≤1000) — the number of queries.

Each of the next t lines contain queries (one query per line).

The query is described as three space-separated integers a,b,k�,�,� (1a,b,k1091≤�,�,�≤109) — the lengths of two types of jumps and the number of jumps, respectively.

Output

Print t integers. The i-th integer should be the answer for the i-th query.

Example
input
Copy
6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999

output
Copy
8
198
-17
2999999997
0
1

Note

In the first query frog jumps 55 to the right, 22 to the left and 55 to the right so the answer is 52+5=85−2+5=8.

In the second query frog jumps 100100 to the right, 11 to the left, 100100 to the right and 11 to the left so the answer is 1001+1001=198100−1+100−1=198.

In the third query the answer is 110+110+1=171−10+1−10+1=−17.

In the fourth query the answer is 1091+1091+1091=2999999997109−1+109−1+109−1=2999999997.

In the fifth query all frog's jumps are neutralized by each other so the answer is 00.

The sixth query is the same as the fifth but without the last jump so the answer is 11.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int t, a, b, k;

int main() {
scanf("%d", &t);
while(t-- != 0) {
scanf("%d %d %d", &a, &b, &k);

int aa = (k + 1) / 2;
int bb = k / 2;

long long res = 1ll * a * aa - 1ll * b * bb;
printf("%lld\n", res);
}

return 0;
}
Copy The Code &

Input

cmd
6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999

Output

cmd
8
198
-17
2999999997
0
1