二维块有三种类型:T 形、H 形和 U 形。它们的具体形状如下图所示:

给定三个非负整数$$$c_T$$$、$$$c_H$$$ 和$$$c_U$$$,分别代表T 形、H 形和U 形块的数量。您的任务是将所有 $$$(c_T + c_H + c_U)$$$ 块打包到 $$$n \times 3$$$ 网格中,遵循以下规则:
- 每个方块必须完全放置在网格内;
- 两个块不能重叠(即,任何单位单元不能被多个块覆盖);
- 块可以是 已旋转 $$$90^{\circ}$$$ 的任意倍数,但它们的边缘必须保持与网格边界平行。
您必须找到存在这种包装的 $$$n$$$ 的最小可能值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含三个整数 $$$c_T$$$、$$$c_H$$$ 和 $$$c_U$$$ ($$$0\le c_T,c_H,c_U\le 10^9$$$, $$$c_T+c_H+c_U \gt 0$$$) — T 形、H 形和分别为U形块。
输出
对于每个测试用例,输出一个整数 - $$$n$$$ 的最小可能值。
示例
输入复制
51 1 12 0 01 1 00 0 10000000001000000000 1000000000 1000000000
输出复制
75530000000007000000000
注意
前三个测试用例的最佳解决方案如下:
