A frog is currently at the point $0$ 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 $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 \le t \le 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 \le a, b, k \le 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



-----Note-----

In the first query frog jumps $5$ to the right, $2$ to the left and $5$ to the right so the answer is $5 - 2 + 5 = 8$.

In the second query frog jumps $100$ to the right, $1$ to the left, $100$ to the right and $1$ to the left so the answer is $100 - 1 + 100 - 1 = 198$.

In the third query the answer is $1 - 10 + 1 - 10 + 1 = -17$.

In the fourth query the answer is $10^9 - 1 + 10^9 - 1 + 10^9 - 1 = 2999999997$.

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

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

Difficulty: introductory

Starter code:

Solutions:
t = int(input())
for i in range(t):
    a, b, k = list(map(int, input().split()))
    ans = (a - b) * (k // 2)
    if k % 2 == 1:
        ans += a
    print(ans)


t = int(input())
for i in range(t):
	a, b, k = list(map(int, input().split()))
	if k % 2 == 0:
		print((a - b) * k // 2)
	else:
		print((a - b) * (k // 2) + a)


T = int(input())
for t in range(T):
    a, b, c = list(map(int, input().split()))
    ans = a * ((c + 1) // 2) - b * (c // 2)
    print(ans)


#from operator import itemgetter
#int(input())
#map(int,input().split())
#[list(map(int,input().split())) for i in range(q)]
#print("YES" * ans + "NO" * (1-ans))
t =  int(input())
for i in range(t):
    a,b,k = list(map(int,input().split()))
    num0 = k // 2
    num1 = k - num0
    print(num1 * a - num0 * b )


t = int(input())
for i in range(t):
    T = input().split(' ')
    a,b,k = int(T[0]), int(T[1]), int(T[2])
    s = (k//2+k%2)*a - (k//2) * b
    print(s)


t = int(input())
for i in range(t):
    a, b, k = map(int, input().split())
    n = k // 2
    mod = k % 2
    print(n * (a - b) + mod * a)

t = int(input())
for cas in range(t):
    a, b, k = map(int, input().split())
    ans = (a-b)*(k//2)
    if(k%2==1):
        ans += a
    print(ans)

t = int(input())

for i in range(t):
	a,b,k = map(int,input().split())
	bc = k//2
	ac = k - bc
	print(a*ac-b*bc)

import sys
from math import floor, ceil

input = sys.stdin.readline

t = int(input())

for zzz in range(t):
    r, l, k = list(map(int, input().split()))

    print(ceil(k/2)*r - floor(k/2)*l)


import math
for _ in range(int(input())):
    a,b,k=list(map(int,input().split()))
    ans=a*math.ceil(k/2)-b*(k//2)
    print(ans)


t = int(input())
for i in range(t):
    a,b,k = map(int, input().split())
    print(a*(k//2 + k%2) - b*(k//2))

I=lambda:list(map(int,input().split()))
for _ in range(int(input())):
    a,b,k=I()
    if k%2==0:
        print((k//2)*(a-b))
    else:
        print((k//2)*(a-b)+a)


import sys
input = sys.stdin.readline

def main():
    t = int(input())
    for i in range(t):
        a, b, k = list(map(int, input().split()))
        if k % 2 == 0:
            answer = a*(k//2) - b*(k//2)
        else:
            answer = a*((k//2) + 1) - b*(k//2)
        print(answer)
    return

def __starting_point():
    main()

__starting_point()

t=int(input())
Q=[list(map(int,input().split())) for i in range(t)]

for a,b,k in Q:
    if k%2==0:
        print((a-b)*k//2)
    else:
        print((a-b)*(k//2)+a)


for _ in range(int(input())):
    a,b,k = map(int,input().split())
    if a == b:
        print(0 if k%2 == 0 else a)
    else:
        if k % 2 == 1:
            print(((k//2)+1)*a - (k//2)*b)
        else:
            print(k//2* a - k//2 * b)

gcd = lambda a, b: gcd(b, a % b) if b else a


def main():
    t = int(input())
    for _ in range(t):
        a, b, c = map(int, input().split())
        total = 0
        total -= b * (c // 2)
        total += a * (c // 2)
        if c % 2:
            total += a
        print(total)




main()

n=int(input())
Q = []
for _ in range(n):
    Q.append(list(map(int,input().split())))

for a,b,k in Q:
	y = int(k/2)
	x = k - y
	print(a*x - b*y)




def main():
    t = int(input())
    for i in range(t):
        a, b, k = map(int, input().split())
        pos = (a - b) * (k // 2)
        pos += a * (k % 2)
        print(pos)

main()

t = int(input())
for i in range(t):
    a, b, k = list(map(int, input().split()))
    ak = (k + 1) // 2
    bk = k - ak
    print(ak * a - bk * b)


for i in range(int(input())):
  a, b, k=map(int, input().split())
  if (k==0):
    print (0)
    continue
  if (k%2==0):
    print (a*(k//2)-b*(k//2))
  else:
    print (a*(k//2+1)-b*(k//2))

#a = map(int, input().split())
t = int(input())
for i in range(t):
    a, b, k = list(map(int, input().split()))
    print((k + 1) // 2 * a - (k // 2) * b)