该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你三个正整数 $a,b,c$，求：

其中 $gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数，$x\space mod\space y$ 表示 $x$ 除以 $y$ 的余数。

输入格式

从文件gcd.in中读取数据。

• 第一行一个正整数 $T$，表示数据组数。
• 接下来 $T$ 行，每行三个正整数 $a,b,c$。

输出格式

输出到文件gcd.out中。

• 输出 $T$ 行，表示每组数据的答案。

3
2 3 4
6 9 10
233 666 999

1
5
145107752

数据规模与约定

• 对于测试点 $1\sim 4$：$1\le T\le 5,2\le a\le 9,1\le b,c\le 18$。
• 对于测试点 $5\sim 8$：$1\le T\le 5,2\le a\le 9,1\le b,c\le 100$。
• 对于测试点 $9\sim 12$：$1\le T\le 5,2\le a\le 9,1\le b\lt 10^5,c=b+1$。
• 对于测试点 $13\sim 20$：$1\le T\le 10^5,2\le a\le 10^9,1\le b,c\le 10^9$。