시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB128503734.579%

문제

래환이는 창하를 위해 초콜릿을 포장하려고 한다. 그림 (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$의 최솟값을 출력한다.

예제 입력 1

4
2 1 1
0 0 1
1 5 0
4 2 2

예제 출력 1

4
3
6
7

첫 번째 테스트 케이스의 경우, $A = 2$, $B = 1$, $C = 1$일 때 $N = 4$이면 주머니에 모든 초콜릿을 담을 수 있으며 $N < 4$이면 주머니에 모든 초콜릿을 담을 수 없다.