Butters thinks he is really smart. So he gave gave three numbers to Cartman, A B and N such that A is the first term of an A.P. (Arithmetic Progression), B is the second term of that A.P. and N is the number of terms in the A.P. Then he asked him to find the sum of all the elements in that A.P. Can you find the sum for him?

Input

First line will contain "T" the number of test cases. Each of the next T lines will contain three integers A, B and N.

Output

For each test case output the sum of all the elements of the A.P. in a separate line.

Constraints

1 <= T <= 100

-10^4 <= A, B <= 10^4

1 <= N <= 1000

Example

Input:
3
3 7 5
2 1 6
4 4 3

Output:
55
-3
12