A person has two piles of stones with him, one has n1 stones and the other has n2 stones. Fired up by boredom, he invented a game with the two piles.
- Before the start of the game person chooses an integer m.
- In the j-th move: He chooses a number xj such that 1 ≤ xj ≤ m, and removes xj stones from both the piles (this is only possible when both the piles have ≥ xj stones).
- The number chosen must be unique over all the moves in the game. That is, for all k < j, xj ≠ xk.
- The game stops when person is unable to make any more moves.
Note: Person wants to make the moves in such a way that the sum of the number of stones remaining in the two piles is minimized.
Please help person find this.
Input
The first line of input contains an integer T denoting the number of test cases.
Each test case consists of 1 line with three integers — n1, n2 and m — separated by single spaces.
Output
For each test case, output a single line containing the minimum sum of the number of stones of two piles.