题目描述

对于正整数 $a, b$，定义 $R(a, b)$ 为：

$\begin{cases}R(b,a)&a<b\\R\left(\left\lfloor\dfrac{a}{b}\right\rfloor,b\right)&1<b\leq a\\a&1=b\leq a\end{cases}$

给定正整数 $g, h$，求正整数 $a, b$ 使得 $\gcd(a,b)=g$，$R(a,b)=h$。

输入格式

第一行一个整数 $T$，代表数据组数。
接下来 $T$ 行每行两个正整数 $g_i, h_i$。

输出格式

输出 $T$ 行，每行两个满足题意的正整数 $a_i, b_i$。
要求 $a, b$ 均不超过 $10^{18}$。
可以证明一定有满足题意的 $a, b$，若有多组解输出任意一组即可。

1
1 4

99 23

2
3 2
5 5

9 39
5 5

提示

【样例解释 #1】

$\gcd(99,23)=1$，$R(99,23)=4$

【数据范围】

对于 $100\%$ 的数据，$1 \leq g \leq 200,000$，$2 \leq h \leq 200,000$。

Subtask #1（$4$ pts）：$g=h$。
Subtask #2（$7$ pts）：$h=2$。
Subtask #3（$7$ pts）：$g=h^2$。
Subtask #4（$14$ pts）：$g,h \leq 20$。
Subtask #5（$36$ pts）：$g,h \leq 2000$。
Subtask #6（$32$ pts）：无附加约束。

【说明】

译自 Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 C Euklid。