49. Make Three Numbers Equal

Difficulty: medium · Math, Greedy

Problem

You are given three integers `P`, `Q` and `R`. In one operation you choose two of the numbers, increase each of them by 1, and decrease the third number by 1. (Numbers may become zero or negative along the way.) Find the minimum number of operations needed to make all three numbers equal, or print `-1` if it is impossible. The input contains several test cases.

Input

- Line 1: the number of test cases `T`. - Next `T` lines: three space-separated integers `P Q R`.

Output

For each test case print the answer on its own line.

Example 1

Input:
4
1 2 3
4 4 4
3 2 6
1 1 7
Output:
-1
0
-1
3

Explanation: 1 2 3 and 3 2 6 mix odd and even numbers, so they are impossible (-1). 4 4 4 is already equal (0). For 1 1 7, three operations each raising the two 1s and lowering 7 give 4 4 4.

Example 2

Input:
1
2 4 4
Output:
2

Explanation: Raise 2 and the first 4 while lowering the second 4: (3, 5, 3). Then raise both 3s and lower 5: (4, 4, 4). Two operations.

Constraints

- 1 <= T <= 10^4 - 1 <= P, Q, R <= 10^9

Solutions are judged against 2 sample and 9 hidden tests. Sign in to solve it · All problems