Лунтик решил попробовать себя в пении. У него есть $$$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$$$.
| Codeforces Round 750 (Div. 2) |
|---|
| Закончено |
