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

Лунтик решил попробовать себя в пении. У него есть $$$a$$$ одноминутных песен, $$$b$$$ двухминутных и $$$c$$$ трёхминутных. Он хочет распределить все песни на два концерта, при этом каждая песня должна быть ровно в одном концерте.

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

Помогите Лунтику найти наименьшую возможную разницу в минутах между длительностями концертов.

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

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

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

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

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

Пример
Входные данные
4
1 1 1
2 1 3
5 5 5
1 1 2
Выходные данные
0
1
0
1
Примечание

В первом наборе входных данных Лунтик может на первом концерте исполнить одноминутную и двухминутную песни, а на втором — трехминутную. Тогда разница между длительностями будет равна $$$0$$$.

Во втором наборе входных данных Лунтик может на первом концерте исполнить две одноминутных песни, двухминутную песню и трехминутную песню, а на втором — две трехминутных. Тогда длительность первого концерта будет $$$1 + 1 + 2 + 3 = 7$$$, длительность второго будет $$$6$$$. Разница между ними $$$|7-6| = 1$$$.