Apple likes to visit Hammoudeh's home that is near his house, suddenly when Apple saw Hammoudeh he gave him the following task:

The task required Hammoudeh to have 3 piles of stones in front of him, first pile has $\bf{a}$ stones, second pile has $\bf{b}$ stones and the third pile has $\bf{c}$ stones, every turn he can perform one of two operations  

1. Choose 2 non-empty piles and take one stone from each pile.  

2. If he has at least three stones, return one stone to each pile

Calculate the minimum number of operations Hammoudeh has to perform in order to make all the piles empty or print $-1$ if it's impossible.

The first line of input contains an integer $T$ ($1 \leq T \leq 10^4$), the number of test cases.

The following $T$ lines each contain three integers a , b , c ($0 \le a,b,c \le 10^9$) 

For each test case, output one integer, the minimum number of operations you have to perform in order to make all the piles empty, or -1 if it's impossible.

In the second test case:

First two operation will be taking 2 piles from the second and third pile so now a = 2 , b = 1 , c = 1 , after performing first two operations we have 4 stones so we can perform the second operation and add 1 stone for each pile , but it is not optimal.