题目描述

奥神运动会闭幕搞山林徒步露营，组委会要给选手搭帐篷，规则超严格，每个帐篷​最多住 3 个人​。

现在有三类选手：

• 社恐独行侠：​a 人​，脾气很倔，​必须一人独占一顶帐篷​，帐篷里不能有第二个人；
• 社牛三人组：​b 人​，只爱热闹，​必须凑满整整 3 人住一顶帐篷​，少一个都不愿意，不能住 $1$ 人、$2$ 人帐篷；
• 随缘百搭党：​c 人​，没任何脾气，能单独住、能两人拼、能凑三人满员，随便安排。

现在请你算出：​最少需要搭多少顶帐篷​，能完全满足三类选手的所有住宿要求。

如果无论怎么安排都满足不了所有人的规矩，就输出 ​$-1$ 。

输入格式

第一行输入一个整数 $t$（$1≤t≤10^4$），代表一共有 $t$ 组露营安排需要计算。

接下来 t 行，每行输入三个整数 $a,b,c$（$0≤a,b,c≤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

限制

1s, 1024KiB for each test case.