演唱会

2S 512MB

题目描述

xrf 最近在筹备演唱会。他有 $a$ 首时长为 $1$ 分钟的歌，$b$ 首时长为 $2$ 分钟的歌，$c$ 首时长为 $3$ 分钟的歌。

他想要把所有歌曲分配到两场演唱会中，并且每首歌都恰好属于其中一场。

一场演唱会的持续时间定义为分配到这场演唱会中的所有歌曲时长之和。xrf 希望这两场演唱会的持续时间之差的绝对值尽可能小。

请你帮助 xrf，求出两场演唱会持续时间之间可能的最小差值（单位：分钟）。

数据范围

• $1 \le t \le 1000$
• $1 \le a,b,c \le 10^9$

对于部分数据：

• $40$ 的数据满足：$t \le 100,\ a,b,c \le 10000$
• $100$ 的数据满足：$t \le 1000,\ a,b,c \le 10^9$

输入格式

从标准输入按以下格式读取数据：

$t$

$a$ $b$ $c$

其中：

• 第一行输入一个整数 $t$，表示测试数据组数。
• 对于每组测试数据，输入一行三个整数 $a,b,c$，分别表示时长为 $1$ 分钟、$2$ 分钟和 $3$ 分钟的歌曲数量。

输出格式

对于每组测试数据，输出一行一个整数，表示两场演唱会持续时间之间可能的最小差值（单位：分钟）。

样例

4
1 1 1
2 1 3
5 5 5
1 1 2

0
1
0
1