题目描述

题目

组委会计划在游览结束后带领奥林匹克运动会的参赛选手进行徒步旅行。目前，正在计算需要搭乘的帐篷数量。据了解，每个帐篷最多可容纳 $3$ 人。

在参赛选手中，有 $a$ 名内向型选手， $b$ 名外向型选手和 $c$ 名没有要求的选手：

• 每个内向选手都想独自住在帐篷里。因此，内向选手的帐篷里必须只有一个人--就是他自己。
• 每个外向者都希望和两个人住在一个帐篷里。因此，一个外向者的帐篷里必须正好有三个人。
• 每个人都可以选择任何一种方式(独居或者与他人同住)。

请问至少需要多少顶帐篷，才能让所有参加者都能根据自己的喜好找到住处。如果无法满足所有参赛者的愿望，则输出 $-1$ 。

输入格式

每个测试由多个测试用例组成。第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例的数量。随后是测试用例的说明。

每个测试用例由一行描述，其中包含三个整数 $a$ 、 $b$ 、 $c$ ( $0 \le a, b, c \le 10^9$ )--分别是内向型、外向型和通用型的数量。

输出格式

对于每个测试用例，输出一个整数，即最小帐篷数，如果无法容纳参赛者，则输出 $-1$ 。

样例

10
1 2 3
1 4 1
1 4 2
1 1 1
1 3 2
19 7 18
0 0 0
7 0 0
0 24 0
1000000000 1000000000 1000000000

3
-1
3
-1
3
28
0
7
8
1666666667