题目描述

译自 COCI 2020/2021 Contest #2 T3「Euklid」

很少有人提到 Euclid 的祖母来自克罗地亚的 Vrsi，Euclid 的堂兄 Edicul 正是来自于那里。

有一天，他们在玩一个叫「发明算法」的游戏。Edicul 的算法是这样的：首先他在沙滩下写下了两个数 $a,b$，接下来对这两个数作如下处理：如果 $a < b$，他将 $a,b$ 交换，否则他令 $a=\left \lfloor \dfrac{a}{b} \right \rfloor$。Edicul 将会重复上述过程直到有一个数变成 $1$，此时另外一个数就是他的算法的结果。

形式化地说，设 $a,b$ 均为正整数，则 Edicul 的算法的结果 $R(a,b)$ 将会是这样的：

$$R(a,b)= \begin{cases} R(b,a) & \text{ if } a < b \\ R \left( \:\!\!\left\lfloor \:\!\!\dfrac{a}{b}\:\!\! \right\rfloor\! , b \right) & \text{ if } a \geq b > 1 \\ a & \text{ if } a \geq b = 1 \end{cases} $$

Euclid 思考了一会，说道：「Edicul，我有一个更好的想法……」，剩下的故事大家都知道了。Euclid 求最大公约数的辗转相除法在数论史上留下了浓墨重彩的一笔，但不幸的是，Edicul 的算法却几乎被人遗忘。

在听完这个故事之后，你需要解决这个问题：给出正整数 $g,h$，你需要求出正整数 $a,b$，使得 $\gcd(a,b)=g$，$R(a,b)=h$。

输入格式

输入第一行一个整数 $t$，代表数据组数。

接下来 $t$ 行，每行两个整数 $g_i,h_i$。

输出格式

输出 $t$ 行。对于第 $i$ 组数据，输出两个整数 $a_i,b_i$ 使得 $\gcd(a_i,b_i)=g_i$，$R(a_i,b_i)=h_i$。

你输出的 $a_i,b_i$ 要求不得超过 $10^{18}$。可以证明在题目的数据范围内，总是存在满足条件的解。

如果有多组满足要求的解，你可以任意输出其中一个。

1
1 4

99 23

2
3 2
5 5

9 39
5 5

数据范围与提示

所有数据均满足：$1 \leq g_i \leq 2 \times 10^5$，$2 \leq h_i \leq 2 \times 10^5$。

各子任务的分值和约束条件如下：

子任务编号	约束	分值
$1$	$g_i=h_i$	$4$
$2$	$h_i=2$	$7$
$3$	$g_i=h_i^2$	$7$
$4$	$g_i,h_i \leq 20$	$14$
$5$	$g_i,h_i \leq 2 \times 10^3$	$36$
$6$	无附加约束	$32$

（分数已折合成百分制）