组委会计划在参观结束后带奥赛参赛者徒步旅行。目前,需要占用的帐篷数量正在计算中。据了解,每个帐篷最多可容纳 $$$3$$$ 人。
参与者中,有 $$$a$$$ 内向者、$$$b$$$ 外向者和 $$$c$$$ 通用者:
- 每个内向的人都想独自住在帐篷里。因此,一个内向者的帐篷必须只容纳一个人——只有内向者本人。
- 每个外向的人都想和另外两个人一起住在一个帐篷里。因此,外向者的帐篷必须恰好容纳三个人。
- 每个通用都可以选择任何选项(独自生活、与另一个人一起生活或与另外两个人一起生活)。
组委会非常尊重每一位参赛者的意愿,所以他们希望能够全部实现。
请告诉我们需要带的最少帐篷数量,以便所有参与者都能根据自己的喜好容纳。如果无法以满足所有愿望的方式容纳参与者,则输出$$$-1$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是测试用例的描述。
每个测试用例由一行描述,其中包含三个整数 $$$a$$$、$$$b$$$、$$$c$$$ ($$$0 \le a, b, c \le 10^9$$$)——分别是内向者、外向者和共性者的数量。
输出
对于每个测试用例,输出一个整数 - 帐篷的最小数量,如果无法容纳参与者,则输出 $$$-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$$$ 帐篷将提供给内向者,$$$1$$$ 帐篷将由两个外向者和一个通用者共享,最后一个帐篷将由两个通用者共享。总共需要 $$$3$$$ 帐篷。
在第二个测试用例中,三个外向者将乘坐 $$$1$$$ 帐篷,而一个内向者将乘坐 $$$1$$$ 帐篷。然后,就会剩下一名外向型和一名通用型。这个外向的人将无法与另外两个人一起生活。