该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

求一棵有 $a+b+c$ 个点的有根树的最小高度，满足下列条件：

• 有 $a$ 个点恰好有 $2$ 个儿子；
• 有 $b$ 个点恰好有 $1$ 个儿子；
• 有 $c$ 个点没有儿子（叶子）。

如果不存在这样的树，需要报告。

上图中树根在最上方，每个点旁边标的是它的儿子个数。这里 $a=2$、$b=1$、$c=3$，树的高度为 $2$。

$^{\dagger}$ 有根树是连通、无环的图，其中有一个特殊的点叫根。在有根树中，任意一条边连接的两个点里，离根更近的那个叫父节点，另一个叫子节点。

树上两点的距离是它们之间最短路径上的边数。有根树的高度是树上任意一点到根的距离的最大值。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示数据组数。

每组数据只有一行，包含三个整数 $a$、$b$、$c$（$0 \leq a, b, c \leq 10^5$；$1 \leq a + b + c$）。

所有测试数据的 $a+b+c$ 之和不超过 $3 \cdot 10^5$。

输出格式

对每组数据：若不存在这样的树，输出 $-1$；否则输出一个整数，表示满足条件的最小高度。

说明

第一组数据在题面图中给出，可以证明高度不可能小于 $2$。

第二组数据可以构造只含一个点、没有边的树，高度为 $0$，显然最优。

第三组数据可以构造两个点、一条边的树，高度为 $1$，显然最优。

样例

10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1

2
0
1
1
-1
3
6
-1
-1
3

来源

Codeforces Round 937 (Div. 4) F 题