Problem: 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 ≤ t ≤ 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 ≤ a, b, k ≤ 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.

Solution (in PYTHON):

Solution:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    from math import gcd
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    def gcd(x, y):
        """gcd(x, y) -> int
        greatest common divisor of x and y
        """
        while y:
            x, y = y, x % y
        return x

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


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


if __name__ == '__main__':
    sync_with_stdio(False)

    if 'PyPy' in sys.version:
        from _continuation import continulet

        def bootstrap(c):
            callable, arg = c.switch()
            while True:
                to = continulet(lambda _, f, x: f(x), callable, arg)
                callable, arg = c.switch(to=to)

        c = continulet(bootstrap)
        c.switch()

        main()

    else:
        import threading

        sys.setrecursionlimit(2097152)
        threading.stack_size(134217728)

        main_thread = threading.Thread(target=main)
        main_thread.start()
        main_thread.join()