CF1582A.Luntik and Concerts

Luntik has decided to try singing. He has $a$ one-minute songs, $b$ two-minute songs and $c$ three-minute songs. He wants to distribute all songs into two concerts such that every song should be included to exactly one concert.

He wants to make the absolute difference of durations of the concerts as small as possible. The duration of the concert is the sum of durations of all songs in that concert.

Please help Luntik and find the minimal possible difference in minutes between the concerts durations.

伦蒂克决定尝试唱歌。他有 $a$ 首时长为一分钟的歌曲、$b$ 首时长为两分钟的歌曲和 $c$ 首时长为三分钟的歌曲。他希望将所有歌曲分配到两场音乐会中，使得每首歌恰好被分配到其中一场音乐会。

他希望使两场音乐会的总时长之差的绝对值尽可能小。一场音乐会的时长等于该场音乐会中所有歌曲时长的总和。

请帮助伦蒂克，求出两场音乐会时长之差（单位：分钟）的最小可能值。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Each test case consists of one line containing three integers $a, b, c$ $(1 \le a, b, c \le 10^9)$ — the number of one-minute, two-minute and three-minute songs.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例由一行组成，包含三个整数 $a, b, c$（$1 \le a, b, c \le 10^9$）—— 分别表示时长为一分钟、两分钟和三分钟的歌曲数量。

For each test case print the minimal possible difference in minutes between the concerts durations.

对于每个测试用例，输出两场音乐会时长之间可能的最小时间差（单位：分钟）。

In the first test case, Luntik can include a one-minute song and a two-minute song into the first concert, and a three-minute song into the second concert. Then the difference will be equal to $0$.

In the second test case, Luntik can include two one-minute songs and a two-minute song and a three-minute song into the first concert, and two three-minute songs into the second concert. The duration of the first concert will be $1 + 1 + 2 + 3 = 7$, the duration of the second concert will be $6$. The difference of them is $|7-6| = 1$.

在第一个测试用例中，Luntik 可以将一首时长为一分钟的歌曲和一首时长为两分钟的歌曲放入第一场音乐会，将一首时长为三分钟的歌曲放入第二场音乐会。此时两场音乐会的时长差为 $0$。

在第二个测试用例中，Luntik 可以将两首时长为一分钟的歌曲、一首时长为两分钟的歌曲和一首时长为三分钟的歌曲放入第一场音乐会，将两首时长为三分钟的歌曲放入第二场音乐会。第一场音乐会的总时长为 $1 + 1 + 2 + 3 = 7$，第二场音乐会的总时长为 $6$。它们的时长差为 $|7-6| = 1$。