塔子哥是一个年轻的数学学生,他非常喜欢数学并且很擅长解决各种数学难题。最近,他开始研究最大公约数,希望能够找到更加高效的方法来解决这个问题。
他花了很长时间研究最大公约数的性质和应用,但一直没有找到一个很好的解决方法。他感到非常沮丧,觉得自己的数学能力还不够强。
有一天,他偶然遇到了一位老师,这位老师是一名资深的数学家,曾经在最大公约数的研究方面有很大的成就。塔子哥向老师请教如何找到两个数的最大公约数。
老师告诉他,要找出两个数的最大公约数,可以先用较大的数去除较小的数,然后用余数去除较小的数,一直重复这个步骤,直到余数为零为止。这个时候,较小的数就是这两个数的最大公约数。
塔子哥非常惊喜,他觉得这个方法非常简单而又高效。他马上回到家中,开始运用老师教给他的方法,解决各种数学难题。
现在塔子哥给出两个整数 a 和 b , 你现在有k 次操作,每次要么选择a,使其自增1,要么选择b使其自增1.
现在塔子哥想知道,执行完 k 次操作后, a 和 b 的最大公约数最大可以是多少?
输入包含 T 组测试用例,第一行一个整数 T 。
每行一组组测试用例,输入三个整数 a , b , k 。
1≤T≤20
1≤a,b,k≤100000
输出 T 行,每行一个整数,代表一个测试用例的答案。
输入
5
1 6 3
3 5 7
8 9 3
12 23 5
17 31 17
输出
2
5
10
8
13
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.