题目内容

塔子哥是一个年轻的数学学生，他非常喜欢数学并且很擅长解决各种数学难题。最近，他开始研究最大公约数，希望能够找到更加高效的方法来解决这个问题。

他花了很长时间研究最大公约数的性质和应用，但一直没有找到一个很好的解决方法。他感到非常沮丧，觉得自己的数学能力还不够强。

有一天，他偶然遇到了一位老师，这位老师是一名资深的数学家，曾经在最大公约数的研究方面有很大的成就。塔子哥向老师请教如何找到两个数的最大公约数。

老师告诉他，要找出两个数的最大公约数，可以先用较大的数去除较小的数，然后用余数去除较小的数，一直重复这个步骤，直到余数为零为止。这个时候，较小的数就是这两个数的最大公约数。

塔子哥非常惊喜，他觉得这个方法非常简单而又高效。他马上回到家中，开始运用老师教给他的方法，解决各种数学难题。

现在塔子哥给出两个整数 $a$ 和 $b$ , 你现在有$k$ 次操作，每次要么选择$a$，使其自增1，要么选择$b$使其自增1.

现在塔子哥想知道，执行完 $k$ 次操作后， $a$ 和 $b$ 的最大公约数最大可以是多少?

输入描述

输入包含 $T$ 组测试用例，第一行一个整数 $T$ 。

每行一组组测试用例，输入三个整数 $a$ , $b$ , $k$ 。

$1\leq T \leq 20$

$1\leq a,b,k \leq 100000$

输出描述

输出 $T$ 行，每行一个整数，代表一个测试用例的答案。

样例

输入

5
1 6 3
3 5 7
8 9 3
12 23 5
17 31 17

输出

2
5
10
8
13