Frog Jumping

A frog is currently at the point $0$ on a coordinate axis $O x$ . 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 $x - b$ .

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$ ( $1 \leq t \leq 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$ ( $1 \leq a, b, k \leq 10^{9}$ 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

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

Output

8
198
-17
2999999997
0
1

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {

int t;

cin >> t;

while (t--) {

long long a, b, k;

cin >> a >> b >> k;

long long ans;

if (k % 2 == 0) {

ans = (k / 2) * a - (k / 2) * b;

} else {

ans = (k / 2 + 1) * a - (k / 2) * b;

}

cout << ans << endl;

}

return 0;

}

Comments