Problem Statement

We have $R$ red balls, $G$ green balls, and $B$ blue balls. You can do the following operation any number of times:

• choose two balls of different colors and turn them into two balls of the remaining color.

For example, you can choose a red ball and a blue ball and turn them into two green balls.

Your objective is to make all balls have the same color. Determine whether this objective is achievable. If it is, find the minimum number of operations required to achieve it.

For each input file, solve $T$ test cases.

Constraints

• $1 \leq T \leq 100$
• $1 \leq R,G,B \leq 10^8$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is in the following format:

R G B

Output

For each case, print -1 if the objective is unachievable; otherwise, print the minimum number of operations to achieve it.