题目内容

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

现在Dash想知道，执行完 $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