Luntik 决定尝试唱歌。他有 $$$a$$$ 一分钟歌曲、$$$b$$$ 两分钟歌曲和 $$$c$$$ 三分钟歌曲。他希望将所有歌曲分发到两场音乐会中,以便每首歌曲都应该包含在一场音乐会中。
他想让音乐会持续时间的绝对差异尽可能小。音乐会的持续时间是该音乐会中所有歌曲的持续时间之和。
请帮助 Luntik 找出音乐会持续时间之间可能存在的最小分钟差异。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含三个整数 $$$a, b, c$$$ $$$(1 \le a, b, c \le 10^9)$$$ — 一分钟、两分钟和三分钟歌曲的数量。
输出
对于每个测试用例,打印音乐会持续时间之间可能的最小分钟差异。
示例
输入 #1
4 1 1 1 2 1 3 5 5 5 1 1 2
输出 #1
0 1 0 1
注意
在第一个测试用例中,Luntik 可以在第一场音乐会中包含一首一分钟的歌曲和一首两分钟的歌曲,在第二场音乐会中包含一首三分钟的歌曲。那么差值将等于$$$0$$$。
在第二个测试用例中,Luntik 可以在第一场音乐会中包含两首一分钟歌曲、一首两分钟歌曲和一首三分钟歌曲,以及在第二场音乐会中包含两首三分钟歌曲。第一场音乐会的持续时间为$$$1 + 1 + 2 + 3 = 7$$$,第二场音乐会的持续时间为$$$6$$$。它们的区别是$$$|7-6| = 1$$$。