题目描述

给定 $N(1 ≤ N ≤ 100)$ 对整数，每组有两个整数，求每对整数的最大公约数与最小公倍数。

求最大公约数(GCD)与最小公倍数(LCM)有很多方法，这里介绍的是辗转相除法，也称为欧几里德算法，是一种用于求解两个正整数最大公约数的有效算法。其基本思想是通过重复使用取余操作来逐步缩小两个整数的范围，直到得到最大公约数，由于其高效性和简洁性，常用于编程和数学等领域。

最小公倍数可以在求得最大公约数后，根据公式：a * b == GCD * LCM，即LCM = a * b / GCD得来，为防止a * b的计算超过整数类型的表示范围，建议通过LCM = a / GCD * b计算而来。

辗转相除法的数学原理：对于整数a、b和余数r（r = a % b），如果a能被b整除（即a % b == 0），那么b就是a和b的最大公约数。否则，最大公约数等于b和r的最大公约数。 辗转相除法的步骤如下：

1. 选取两个正整数a和b作为输入。
2. 计算a除以b的余数，用r表示，即r = a % b。
3. 若r为0，则b就是最大公约数，算法结束，返回b。
4. 若r不为0，则将b赋值给a，将r赋值给b，然后返回第2步，继续执行。
5. 重复执行步骤2、3、4，直到余数r等于0为止。最终，辗转相除法得到的b即是a和b的最大公约数。

3
45 60
99 36
2345 789

15 180
9 396
1 1850205