Description

For positive integers $a, b$, define $R(a, b)$ as:

$\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}$

Given positive integers $g, h$, find positive integers $a, b$ such that $\gcd(a,b)=g$ and $R(a,b)=h$.

Input Format

The first line contains an integer $t\ (1\leq t\leq40)$, the number of test cases.
The next $t$ lines each contain two positive integers $g_i, h_i$.

Output Format

Output $t$ lines, each containing two positive integers $a_i, b_i$ that satisfy the requirements.
Both $a$ and $b$ must not exceed $10^{18}$.
It can be proven that such $a, b$ always exist. If there are multiple solutions, output any one of them.

1
1 4

99 23

2
3 2
5 5

9 39
5 5

Hint

Sample Explanation #1

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

Constraints

For $100\%$ of the testdata, $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): no additional constraints.

Notes

Translated from Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 C Euklid。

Translated by ChatGPT 5