Statement

Alex is passionate about diverse mathematical challenges, and as a gift for you to start the new IIOT season, he gives you three positive integers A, B and K. He tells you that you must use exactly K increments (i.e., increasing a value by one) on A and B, in any way you want. Now, he wants to find the greatest possible value of the greatest common divisor of the two integers obtained after the increments. For example, if A = 7, B = 11 and K = 3, the answer is 7, because we can use all 3 increments on B to make it equal to 14 and gcd(7, 14) = 7. However, if A = 18, B = 9 and K = 3, the answer is 10 (A = 20, B = 10 after incrementing the values 3 times). Alex decided to test you on T such triplets. Show Alex that math is your friend as well!