题目描述

刘校长计划在比赛结束后带领卉图奥赛班的参赛选手进行徒步旅行。目前，正在计算需要搭乘的帐篷数量。据了解，每个帐篷最多可容纳 $3$ 人。

在参赛选手中，有 $a$ 名社恐型选手， $b$ 名社牛型选手，以及 $c$ 名无所谓型选手：

• 每个社恐都想独自住在帐篷里。因此，社恐的帐篷里必须只有一个人 -- 只有社恐自己。
• 每个社牛都想和另外两个人住在一个帐篷里。因此，一个社牛的帐篷里必须正好有三个人。
• 无所谓选手可以选择任何一种方式（独居、与两人同住或与三人同住）。

刘校长非常尊重每位选手的意愿，因此他们希望满足所有选手的愿望。

请你告诉刘校长，至少需要多少顶帐篷，以便所有选手都能根据自己的喜好找到住处。如果无法满足所有选手的愿望，请输出 $-1$ 。

输入格式

每个测试由多个测试用例组成。第一行包含一个整数 $t$ - 测试用例数。随后是测试用例的说明。

每个测试用例由一行描述，包含三个整数 $a$ , $b$ , $c$ --分别是社恐型选手、社牛型选手和无所谓型选手的数量。

输出格式

对于每个测试用例，输出一个整数 - 最小帐篷数，如果无法满足所有选手的需要，则输出 $-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

说明

• 在第一个测试案例中， $1$ 顶帐篷将分配给社恐型选手， $1$ 顶帐篷将由两个社牛型选手和一个无所谓型选手共享，最后一顶帐篷将由两个无所谓型选手共享。总共需要 $3$ 顶帐篷。
• 在第二个测试案例中，三个社牛型选手将使用 $1$ 个帐篷，一个社恐型选手将使用 $1$ 个帐篷。然后，剩下一个社牛型选手和一个无所谓型选手。这个社牛型选手将无法与另外两个人一起共享。

数据范围

对于 $100\%$ 的测试数据，$1 \le t \le 10^4$, $0 \le a, b, c \le 10^{10}$