34126번 - 래환이의 초콜릿 포장 이야기

문제

래환이는 창하를 위해 초콜릿을 포장하려고 한다. 그림 (a)와 같이 1ドル \times 1,ドル 1ドル \times 2,ドル 1ドル \times 3$ 크기의 초콜릿이 각각 $A,ドル $B,ドル $C$개 있으며, 래환이는 그림 (b)와 같은 $N \times 2$ 모양의 주머니에 초콜릿 모두를 담고 싶어 한다. 단, 초콜릿은 중력의 영향을 받기 때문에 위에서부터 하나씩 넣어야 하며, 공중에 떠 있게 둘 수는 없다. 즉, 모든 초콜릿은 바닥 또는 이미 들어간 다른 초콜릿 위에 닿아 있어야 한다.

또한, 초콜릿은 (a)에 그려진 방향대로 넣거나 90ドル$도 회전해서만 넣을 수 있다. 따라서 넣을 수 있는 모든 초콜릿의 모양은 1ドル \times 1,ドル 1ドル \times 2,ドル 2ドル \times 1,ドル 3ドル \times 1$ 중 하나이다. 그림 (c)는 주머니에 초콜릿을 담은 상태를 나타낸 것이다.

래환이는 주머니 밖으로 초콜릿이 넘어가지 않도록 하는 양의 정수 $N$의 최솟값을 구하고 싶다. 래환이는 얼마나 큰 주머니를 사용해야 할까?

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다. $(1 \le T \le 5 \times 10^5)$

각 테스트 케이스의 첫 번째 줄에 세 개의 정수 $A,ドル $B,ドル $C$가 공백으로 구분되어 주어진다. 단, $A + B + C > 0$이다. $(0 \le A, B, C \le 10^8)$

출력

각 테스트 케이스마다 주머니의 높이를 나타내는 양의 정수 $N$의 최솟값을 출력한다.

제한

힌트