演唱会

题目描述:

xrf最近在筹备演唱会。他有a首长达1分钟的歌，b首长达两分钟的歌，c首长达3分钟的歌。他想要把所有的歌分配到两场演唱会里边，使得每首歌都正好包含在一场演唱会当中。

他想要使两场演唱会的持续时间的绝对差异尽可能小，演唱会的持续时间是该音乐会中所有歌曲的持续时间之和。

请帮助xrf，找出演唱会持续时间之间可能的最小差异（分钟）。

输入格式:

第一行包含一个整数t（1 ≤ t ≤ 1000）--测试案例的数量。
每个测试案例由一行包含三个整数a,b,c（1 ≤ a, b, c ≤ 10⁹ ）--一分钟、两分钟和三分钟的歌曲数量。

输出格式:

对于每个测试案例，输出演唱会持续时间之间的最小可能差异（分钟）。

数据范围:

40%：\(t \leq 100, a, b, c  \leq 10000\)

100%：\(t \leq 1000, a, b, c  \leq 10^9\)

样例输入:

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

样例输出:

0
1
0
1

时间限制: 2000ms
空间限制: 512MB

---

来源: 25年比赛小学组t3