题目描述

有 $a$ 个 $1$ 分钟的音乐，$b$ 个 $2$ 分钟的音乐，$c$ 个 $3$ 分钟的音乐，将这些音乐分成 $2$ 组，使两组音乐的总时长之差的绝对值尽可能小。

输入格式

第一行输入一个正整数 $t$ 表示数据组数。

输出格式

对于每组数据输出一行一个整数表示两组音乐的总时长之差的绝对值的最小值。

说明/提示

$1\le t\le1000,1\le a,b,c\le10^9$。

样例解释：

1. 第一组 $1$ 个 $1$ 分钟音乐、$2$ 个 $2$ 分钟音乐，第二组 $1$ 个 $3$ 分钟音乐时两组音乐总时长之差的绝对值最小，为 $0$。
2. 第一组 $2$ 个 $1$ 分钟音乐、$1$ 个 $2$ 分钟音乐$1$ 个 $3$ 分钟音乐，第二组 $2$ 个 $3$ 分钟音乐时两组音乐总时长之差的绝对值最小，为 $1$。
3. 第一组 $5$ 个 $1$ 分钟音乐、$5$ 个 $2$ 分钟音乐，第二组 $5$ 个 $3$ 分钟音乐时两组音乐总时长之差的绝对值最小，为 $0$。
4. 第一组 $1$ 个 $1$ 分钟音乐、$1$ 个 $3$ 分钟音乐，第二组 $1$ 个 $2$ 分钟音乐、$1$ 个 $3$ 分钟音乐时两组音乐总时长之差的绝对值最小，为 $1$。

样例

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

0
1
0
1