B. Три кучки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру с тремя кучами камней. Изначально у Алисы есть $$$a$$$ камней, у Боба есть $$$b$$$ камней, а третья куча содержит $$$c$$$ камней.

Алиса и Боб ходят по очереди, при этом Алиса ходит первой. На каждом ходу текущий игрок может взять любое количество камней из третьей кучи, возможно, ноль, и добавить их в свою кучу.

Если оба игрока подряд взяли по нулю камней на двух последовательных ходах, игра заканчивается.

Пусть $$$A$$$ и $$$B$$$ — итоговое количество камней у Алисы и Боба соответственно. Результат игры равен $$$|A-B|$$$.

Алиса хочет максимизировать результат, а Боб хочет его минимизировать. Предполагая, что оба игрока играют оптимально, найдите итоговый результат.

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

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

Каждый набор входных данных содержит три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ ($$$0 \le a,b,c \le 10^9$$$) — начальное количество камней у Алисы, у Боба и в третьей куче соответственно.

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

Для каждого набора входных данных выведите одно целое число — итоговый результат, если оба игрока играют оптимально.

Важно использовать $$$64$$$-битный целочисленный тип, например long long в C++.

Пример
Входные данные
5
3 6 3
3 6 10
5 5 4
2 5 6
67676767 41414141 998244353
Выходные данные
3
7
4
3
1024506979
Примечание

В первом наборе входных данных Алиса может взять $$$0$$$ камней на своём первом ходу. Тогда Боб тоже может взять $$$0$$$ камней, и игра закончится с кучами размеров $$$3$$$ и $$$6$$$. Следовательно, результат может быть равен $$$3$$$. Можно показать, что Алиса не может добиться большего результата, а Боб не может добиться меньшего.

Во втором наборе входных данных Алиса может взять все $$$10$$$ камней из третьей кучи на своём первом ходу. Тогда игра заканчивается с кучами размеров $$$13$$$ и $$$6$$$, поэтому результат равен $$$7$$$.