You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

土拨鼠之家准备春游

题目描述

有 $a$ 只内向土拨鼠, $b$ 只外向土拨鼠和 $c$ 只随和土拨鼠, 其中内向土拨鼠必须独自一个帐篷, 外向土拨鼠所在帐篷必须有三只鼠鼠, 随和土拨鼠可以独自一人, 也可以两人, 也可以三人一个帐篷, 问能否有方案使得所有鼠鼠达成心愿? 如果可以, 最少需要准备多少帐篷?

输入格式

第一行一个整数 $t$ 表示有 $t$ 组数据

接下来 $t$ 行每行三个整数表示 $a, b, c$

输出格式

输出 $t$ 行, 如果能达成心愿, 则输出最少需要准备的帐篷数量, 否则输出 -1.

样例 #1

样例输入 #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

样例输出 #1

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

提示

• $1\le t \le 10000$
• $0 \le a, b, c, \le 10^9$