Problem Statement

A rock-paper-scissors tournament was held with $a+b+c$ participants. Here, $a, b, c$ are non-negative integers with $3\leq a+b+c$.

In the tournament, all participants first stand in a circle. Then, each participant plays "Rock," "Scissors," or "Paper."

For each participant, if the hand they played beats both the hand of the participant to their left and the hand of the participant to their right, that participant becomes a winner. There is not necessarily exactly one winner; there may be zero, or two or more winners.

More formally, a participant becomes a winner if one of the following holds:

• The participant played "Rock," and both the left neighbor and the right neighbor played "Scissors."
• The participant played "Scissors," and both the left neighbor and the right neighbor played "Paper."
• The participant played "Paper," and both the left neighbor and the right neighbor played "Rock."

The following is known about this tournament:

• $a$ participants played "Rock."
• $b$ participants played "Scissors."
• $c$ participants played "Paper."

Under this condition, find the maximum possible number of winners in the tournament.

$T$ test cases are given; solve each of them.

Constraints

• $1\leq T\leq 5\times 10^5$
• $0\leq a, b, c\leq 10^9$
• $3\leq a+b+c$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

a b c

Output

Output one line per test case.

For each test case, output the maximum possible number of winners in the tournament.