311351: CF1973A. Chess For Three

A. Chess For Threetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Three friends gathered to play a few games of chess together.

In every game, two of them play against each other. The winner gets $2$ points while the loser gets $0$, and in case of a draw, both players get $1$ point each. Note that the same pair of players could have played any non-negative number of times (possibly zero). It is also possible that no games were played at all.

You've been told that their scores after all the games were played were $p_1$, $p_2$ and $p_3$. Additionally, it is guaranteed that $p_1 \leq p_2 \leq p_3$ holds.

Find the maximum number of draws that could have happened and print it. If there isn't any way to obtain $p_1$, $p_2$ and $p_3$ as a result of a non-negative number of games between the three players, print $-1$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains three integers $p_1$, $p_2$ and $p_3$ ($0 \leq p_1 \leq p_2 \leq p_3 \leq 30$) — the scores of the three players, sorted non-decreasingly.

Output

For each testcase, print one number — the maximum possible number of draws that could've happened, or $-1$ if the scores aren't consistent with any valid set of games and results.

ExampleInput

7
0 0 0
0 1 1
1 1 1
1 1 2
3 3 3
3 4 5
1 1 10

Output

0
1
-1
2
-1
6
2

Note

In the first example, no games were played at all, so no draws could occur either.

For the second example, exactly one game occurred between the second and the third player and it ended in draw, so the answer is $1$.

It's easy to see that there's no set of games achieving the scores in third example, so the answer for it is $-1$.

**题目大意：**
三人国际象棋：每局比赛两人对弈，胜者得2分，败者得0分，平局每人得1分。同一对选手可能进行任意非负数次对局（可能为零），也可能根本没有进行任何比赛。给定三人最终得分\(p_1, p_2, p_3\)，且满足\(p_1 \leq p_2 \leq p_3\)，求可能发生的最多平局次数。如果不存在任何方式使得三人的得分是通过非负数目的比赛得到的，则输出-1。

**输入数据格式：**
第一行包含一个整数\(t\)（\(1 \le t \le 500\)），表示测试用例的数量。接下来每个测试用例占一行，包含三个非负整数\(p_1, p_2, p_3\)（\(0 \leq p_1 \leq p_2 \leq p_3 \leq 30\)），表示三个玩家的分数，按非递减顺序排列。

**输出数据格式：**
对于每个测试用例，输出一个数字，表示可能发生的最大平局次数，或者如果分数与任何有效的比赛结果不一致，则输出-1。

**示例：**
输入：
```
7
0 0 0
0 1 1
1 1 1
1 1 2
3 3 3
3 4 5
1 1 10
```
输出：
```
0
1
-1
2
-1
6
2
```

**说明：**
- 在第一个示例中，没有进行任何比赛，因此也不可能发生平局。
- 在第二个示例中，第二和第三名玩家之间恰好发生了一局比赛，并以平局结束，所以答案是1。
- 很容易看出，第三个示例中不存在任何比赛组合能够达到这些分数，因此答案是-1。**题目大意：** 三人国际象棋：每局比赛两人对弈，胜者得2分，败者得0分，平局每人得1分。同一对选手可能进行任意非负数次对局（可能为零），也可能根本没有进行任何比赛。给定三人最终得分\(p_1, p_2, p_3\)，且满足\(p_1 \leq p_2 \leq p_3\)，求可能发生的最多平局次数。如果不存在任何方式使得三人的得分是通过非负数目的比赛得到的，则输出-1。 **输入数据格式：** 第一行包含一个整数\(t\)（\(1 \le t \le 500\)），表示测试用例的数量。接下来每个测试用例占一行，包含三个非负整数\(p_1, p_2, p_3\)（\(0 \leq p_1 \leq p_2 \leq p_3 \leq 30\)），表示三个玩家的分数，按非递减顺序排列。 **输出数据格式：** 对于每个测试用例，输出一个数字，表示可能发生的最大平局次数，或者如果分数与任何有效的比赛结果不一致，则输出-1。 **示例：** 输入： ``` 7 0 0 0 0 1 1 1 1 1 1 1 2 3 3 3 3 4 5 1 1 10 ``` 输出： ``` 0 1 -1 2 -1 6 2 ``` **说明：** - 在第一个示例中，没有进行任何比赛，因此也不可能发生平局。 - 在第二个示例中，第二和第三名玩家之间恰好发生了一局比赛，并以平局结束，所以答案是1。 - 很容易看出，第三个示例中不存在任何比赛组合能够达到这些分数，因此答案是-1。