Description

It is rarely mentioned that Euclid’s grandma was from Vrsi in Croatia. It is from there that Euclid’s less known (but equally talented in his youth) cousin Edicul comes from.

It happened one day that they were playing “invent an algorithm”. Edicul writes two positive integers on the sand. Then he does the following: while neither number on the sand is $1$, he marks them as $(a, b)$ so that $a \geq b$. Then the numbers are erased and he writes $( \left \lfloor \dfrac{a}{b} \right \rfloor, b)$ on the sand, and repeats the process. When one of the two numbers becomes $1$, the other is the results of his algorithm.

Formally, if $a$ and $b$ are positive integers, the result $R(a, b)$ of Edicul’s algorithm is:

$$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 thinks for a while, and says: “Edicul, I have a better idea...”, and the rest is history. Unfortunately, Edicul never became famous for his idea in number theory.

This sad story inspires the following problem: Given positive integers $g$ and $h$, find positive integers $a$ and $b$ such that their greatest common divisor is $g$, and the result of Edicul’s algorithm $R(a, b)$ is $h$.

Input Format

The first line contains a single integer $t$($1 \leq t \leq 40$) – the number of independent test cases.

Each of the following $t$ lines contains two positive integers $g_i$ and $h_i$ ($h_i \geq 2$).

Output Format

Output $t$ lines in total. For the $i$-th testcase, output positive integers $a_i$ and $b_i$ such that $\gcd(a_i, b_i) =g_i$ and $R(a_i, b_i) =h_i$.

The numbers in the output must not be larger than $10^{18}$. It can be proven that for the given constraints, a solution always exists.

If there are multiple solutions for some testcase, output any of them.

1
1 4

99 23

2
3 2
5 5

9 39
5 5

Scoring

In all subtasks, $1 \leq g_i \leq 2 \times 10^5$，$2 \leq h_i \leq 2 \times 10^5$.

Subtask	Constraints	Point
$1$	$g_i=h_i$	$4$
$2$	$h_i=2$	$7$
$3$	$g_i=h_i^2$
$4$	$g_i,h_i \leq 20$	$14$
$5$	$g_i,h_i \leq 2 \times 10^3$	$36$
$6$	No additional constraints.	$32$