题目描述

You have $A_1$ sticks of length $1$, $A_2$ sticks of length $2$, and $A_3$ sticks of length $3$. You can perform the following operation any number of times:

• Choose 3 sticks such that they can form a triangle. Use these 3 sticks to make a triangle. Once used, these sticks cannot be used to form other triangles.

To "form a triangle", the lengths of the chosen sticks $a$, $b$, and $c$ must satisfy the triangle inequality: $a + b > c$, $b + c > a$, and $c + a > b$.

Determine the maximum number of triangles that can be made.

Given $T$ test cases, compute the answer for each.

输入格式

The input is given in the following format:

$$\begin{aligned} &T \\ &\text{case}_1 \\ &\text{case}_2 \\ &\vdots \\ &\text{case}_T \end{aligned} $$

Here, $\text{case}_i$ denotes the $i$-th test case.

Each test case is given in the following format:

$$A_1 \ A_2 \ A_3$$

• $1 \leq T \leq 10,000$
• $0 \leq A_i \leq 10^8$
• All input values are integers.

输出格式

Output $T$ lines. On the $i$-th line, output the answer for the $i$-th test case.

4
3 1 2
4 1 1
0 0 0
31415926 535897 93238462

2
1
0
41730095