Chef and the stones

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has two piles of stones with him, one has n_{1} stones and the other has n_{2} stones. Fired up by boredom, he invented a game with the two piles.
Before the start of the game Chef chooses an integer m.
In the jth move:
 He chooses a number x_{j} such that 1 ≤ x_{j} ≤ m, and removes x_{j} stones from both the piles (this is only possible when both the piles have ≥ x_{j} stones).
 The number chosen must be unique over all the moves in the game. That is, for all k < j, x_{j} ≠ x_{k}.
Chef 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 Chef 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 — n_{1}, n_{2} 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.
Constraints
Subtask 1 : (5 pts)
 1 ≤ T ≤ 100
 0 ≤ m ≤ 18
 0 ≤ n_{1}, n_{2} ≤ 100
Subtask 2 : (25 pts)
 1 ≤ T ≤ 1000
 0 ≤ m ≤ 10000
 0 ≤ n_{1}, n_{2} ≤ 10000
Subtask 3 : (70 pts)
 1 ≤ T ≤ 10^{5}
 0 ≤ m ≤ 10^{9}
 0 ≤ n_{1}, n_{2} ≤ 10^{18}
Example
Input: 3 1 1 1 1 2 1 4 5 2 Output: 0 1 3
Explanation
Example case 1. : Remove 1 stone from each of the piles. Now 0 stones are remaining, so chef cannot remove any more stones from the piles. Hence, answer is 0+0 = 0
Example case 2. : Again, remove 1 stone from both the piles to get (0,1) stones. Now chef cannot remove any more stones from pile 1, so he stops. Hence, answer is 0+1 = 1.
Example case 3. : First remove 1 stone from both the piles to get (3,4) stones. Now, remove 2 stones from both the piles so that (1,2) stones are remaining. Now chef cannot remove any more stones owing to the condition that he cannot remove the same number of stones twice. So, the answer is 1+2 = 3.
Author:  tapasjain01 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFST 
Tags  adhoc, arithmetic, cakewalk, dec15, greedy, tapasjain01 
Date Added:  31072015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions