Chess For Three

In every game, two of them play against each other. The winner gets $2$ points while the loser gets $0$ , and in case of a draw, both players get $1$ point each. Note that the same pair of players could have played any non-negative number of times (possibly zero). It is also possible that no games were played at all.

You've been told that their scores after all the games were played were $p_{1}$ , $p_{2}$ and $p_{3}$ . Additionally, it is guaranteed that $p_{1} \leq p_{2} \leq p_{3}$ holds.

Find the maximum number of draws that could have happened and print it. If there isn't any way to obtain $p_{1}$ , $p_{2}$ and $p_{3}$ as a result of a non-negative number of games between the three players, print $- 1$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \leq t \leq 500$ ). The description of the test cases follows.

The first line of each test case contains three integers $p_{1}$ , $p_{2}$ and $p_{3}$ ( $0 \leq p_{1} \leq p_{2} \leq p_{3} \leq 30$ ) — the scores of the three players, sorted non-decreasingly.

Output

For each testcase, print one number — the maximum possible number of draws that could've happened, or $- 1$ if the scores aren't consistent with any valid set of games and results.

Example

Input

0 0 0

0 1 1

1 1 1

1 1 2

3 3 3

3 4 5

1 1 10

Output

Solution

#include <iostream>

using namespace std;

int main() {

int a;

cin >> a;

int b = 1, c = 2;

bool ok = true;

while (a--) {

int w;

cin >> w;

if (!ok) {

continue;

}

if (w == b or w == c) {

c = 6 - b - c;

b = w;

} else {

ok = false;

}

if (ok) {

cout << "YES" << endl;

} else {

cout << "NO" << endl;

}

return 0;

}

Comments