题目描述

有三种颜色的球，红色有 $R$ 个，绿色有 $G$ 个，蓝色有 $B$ 个。

每次操作你可以选择两个颜色不同的球（必须存在这两个球，即它们的个数至少为 $1$），将它们变成第三种颜色的球。

例如拿出一个红色和一个绿色的球，把它们变成蓝色。

求最小的操作次数使得所有球的颜色相同，如果无法达成则输出 $-1$。

输入格式

第一行给定一个正整数 $T$，表示数据组数。

之后每组数据，给出三个非负整数 $R,G,B$。

输出格式

对于每组数据，输出一个整数，表示答案

4
1 2 2
1 2 3
1 2 4
1 10 0

2
-1
4
10

数据范围与提示

【样例 1 解释】

• 对于第 $1$ 组数据，$(1, 2, 2) \Rightarrow (3, 1, 1) \Rightarrow (5, 0, 0)$
• 对于第 $2$ 组数据，无法做到，输出 -1
• 对于第 $3$ 组数据，$(1, 2, 4) \Rightarrow (3, 1, 3) \Rightarrow (2, 3, 2) \Rightarrow (1, 5, 1) \Rightarrow (0, 7, 0)$
• 对于第 $4$ 组数据，$(1, 10, 0) \Rightarrow (0, 9, 2) \Rightarrow (2, 8, 1) \Rightarrow (1, 7, 3) \Rightarrow (3, 6, 2) \Rightarrow (5, 5, 1) \Rightarrow (4, 4, 3) \Rightarrow (3, 3, 5) \Rightarrow (2, 2, 7) \Rightarrow (1, 1, 9) \Rightarrow (0, 0, 11)$

【提示】

• 一次操作相当于对 $R, G, B$ 分别执行了 -1, -1, +2
• 我们希望最后能够最后只有一种颜色，必然要将 $R, G, B$ 先转换为 至少有 2 个颜色相同

【数据范围】

对于 $30\%$ 的数据，$0 \leq R,G,B \leq 2$​​。

对于 $60\%$ 的数据，$0 \leq R,G,B \leq 50$

对于 $100\%$ 的数据，$0 \leq R,G,B \leq 10^8,1 \leq T \leq 500$