There are three types of 2D blocks: T-shaped, H-shaped, and U-shaped. Their exact shapes are shown in the figure below:

$\text{[math]}$

You are given three non-negative integers $$$c_T$$$, $$$c_H$$$, and $$$c_U$$$, representing the numbers of T-shaped, H-shaped, and U-shaped blocks, respectively. Your task is to pack all $$$(c_T + c_H + c_U)$$$ blocks into an $$$n \times 3$$$ grid, following these rules:

Every block must be placed entirely inside the grid;
No two blocks may overlap (i.e., no unit cell can be covered by more than one block);
Blocks can be rotated by any multiple of $$$90^{\circ}$$$, but their edges must remain parallel to the grid borders.

You have to find the minimum possible value of $$$n$$$ for which such a packing exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains three integers $$$c_T$$$, $$$c_H$$$, and $$$c_U$$$ ($$$0\le c_T,c_H,c_U\le 10^9$$$, $$$c_T+c_H+c_U \gt 0$$$) — the numbers of T-shaped, H-shaped, and U-shaped blocks, respectively.

Output

For each test case, output a single integer — the minimum possible value of $$$n$$$.

Note

The optimal solutions for the first three test cases are listed below:

$\text{[math]}$

THU Packing Puzzle

Examples