B. Прыгающая лягушка
ограничение по времени на тест
2 с
ограничение по памяти на тест
512 МБ
ввод
стандартный ввод
вывод
стандартный вывод

Сейчас лягушка стоит в позиции $$$0$$$ на координатной оси $$$Ox$$$. Она прыгает по следующему алгоритму: первый прыжок — на $$$a$$$ вправо, второй прыжок — на $$$b$$$ влево, третий прыжок — на $$$a$$$ вправо, четвёртый прыжок — на $$$b$$$ влево, и так далее.

Формально:

  • если лягушка уже прыгнула четное число раз (перед текущим прыжком), то она прыгает от ее текущей позиции $$$x$$$ в позицию $$$x+a$$$;
  • иначе она прыгает от ее текущей позиции $$$x$$$ в позицию $$$x-b$$$.

Ваша задача — найти позицию лягушки после $$$k$$$ прыжков.

Но... Кое-что еще. Вы наблюдаете за $$$t$$$ различными лягушками, так что вам нужно ответить на $$$t$$$ независимых запросов.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество запросов.

Каждая из следующих $$$t$$$ строк содержит запросы (один запрос на строку).

Запрос описывается в виде трех целых чисел $$$a, b, k$$$ ($$$1 \le a, b, k \le 10^9$$$) — длины прыжков двух типов и количество прыжков соответственно.

Выходные данные

Выведите $$$t$$$ целых чисел. $$$i$$$-е число должно быть равно ответу на $$$i$$$-й запрос.

Пример
Входные данные
6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999
Выходные данные
8
198
-17
2999999997
0
1
Примечание

В первом запросе лягушка прыгает на $$$5$$$ позиций вправо, на $$$2$$$ влево и еще раз на $$$5$$$ позиций вправо, таким образом, ответ равен $$$5 - 2 + 5 = 8$$$.

Во втором запросе лягушка прыгает на $$$100$$$ позиций вправо, на $$$1$$$ влево, на $$$100$$$ вправо и еще раз на $$$1$$$ влево, таким образом, ответ равен $$$100 - 1 + 100 - 1 = 198$$$.

В третьем запросе ответ равен $$$1 - 10 + 1 - 10 + 1 = -17$$$.

В третьем запросе ответ равен $$$10^9 - 1 + 10^9 - 1 + 10^9 - 1 = 2999999997$$$.

В пятом запросе все прыжки лягушки нейтрализуют друг друга, таким образом, ответ равен $$$0$$$.

Шестой запрос почти эквивалентен пятому, но без последнего последнего прыжка, таким образом, ответ равен $$$1$$$.