求满足以下条件的、具有 $$$a+b+c$$$ 顶点的有根树$$$^{\dagger}$$$ 的最小高度:
- $$$a$$$ 顶点恰好有 $$$2$$$ 子节点,
- $$$b$$$ 顶点恰好有 $$$1$$$ 子节点,并且
- $$$c$$$ 顶点恰好有 $$$0$$$ 子节点。
上面的树以顶部顶点为根,每个顶点都标有其子节点的数量。这里$$$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$$$。否则,输出一个整数——满足语句中条件的树的最小高度。
示例
输入 #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
输出 #1
2 0 1 1 -1 3 6 -1 -1 3
注意
第一个测试用例如声明中所示。可以证明,你不可能得到小于$$$2$$$的高度。
在第二个测试用例中,您可以形成一棵具有单个顶点且没有边的树。它的高度为 $$$0$$$,这显然是最佳的。
在第三个测试用例中,您可以形成一棵树,其中两个顶点由一条边连接起来。它的高度为$$$1$$$,这显然是最佳的。