题目描述

给定两个正整数 $a$ 和 $b$ , 求这两个数的最大公约数和最小公倍数，$t$ 组询问。

输入格式

第一行一个正整数 $t$

接下来 $t$ 行，每行两个整数，表示 $a$ 和 $b$

输出格式

$t$ 行，每行两个整数，表示最大公约数和最小公倍数

2
12 15
7 49

3 60
7 49

数据规模与约定

subtask1：$1 \leq t \leq 10^3, 1 \leq a,b \leq 10^3$，30分

subtask2: $1 \leq t \leq 10^5, 1 \leq a,b \leq 10^9$，70分

提示：

1. 暴力枚举
2. 辗转相除法
3. 更相减损术