题目描述

给出两个正整数 $m$ 和 $n$，求出它们的最大公约数。本题中包含多组输入数据。

题目格式

输入

输入有多行。

• 第一行输入一个正整数 $n$（$1 <=n <= 1000$），代表接下来有 $n$ 组测试数据。
• 第二行开始有n行，每行输入两个正整数 $x$ 和 $y$ ($1<=x, y <= 100000$)，两个数字之间用空格隔开。

输出

输出有 $n$ 行，每行代表输入的两个整数的最大公约数。

题目样例

3
6 6
11 12
33 22

6
1
11

题目解释

当输入的第一行数字为 $3$ 时，代表接下来有 $3$ 组数字，第一组数字为 $6 6$，它们的最大公约数为 $6$；第二组数字为 $11 12$，它们的最大公约数为 $1$；第三组数字为 $33 22$，它们的最大公约数为 $11$。

题目提示

1、最大公约数是指两个数字的公因数（公共因数）中最大的那个公因数。 2、求两个数字的最大公因数的方法有欧几里得算法，又称辗转相除法。辗转相处法的具体步骤如下（以求 $128$ 和 $78$ 的最大公约数为例）：

• 开始时：用 大的数字 除以 小的数字 得到 余数；
• 从第二次开始：用 上一次的除数 除以 上一次的余数 得到 新的余数；
• 重复上面过程，直到余数为 $0$ 为止。本次计算的 商 为两个数字的最大公约数。

所以，$128$ 和 $78$ 的最大公约数为 $2$。 3、辗转相除法的资料，点击阅读 4、还有一种求最大公约数的方法叫更相减损术