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\ge b$. Then the numbers are erased and he writes $(\lfloor \frac{a}{b}\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:

$${\displaystyle R(a,b)=\{\begin{array}{ll}R(b,a)& \text{if }a<b\\ R(\lfloor \frac{a}{b}\rfloor ,b)& \text{if }a\ge b>1\\ a& \text{if }a\ge b=1\end{array}}$$

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$.

* This sets up a pun in Croatian. The translation is a bit bland, sorry for that.

Input

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

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

Output

Output $t$ lines in total. For the $i$-th test case, 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 test case, output any of them.

Scoring

In all subtasks, $1\le g\le 200000$ and $2\le h\le 200000$.

Subtask	Score	Constraints
$1$	$4$	$g=h$
$2$	$8$	$h=2$
$3$	$8$	$g=h^2$
$4$	$15$	$g,h\le 20$
$5$	$40$	$g,h\le 2000$
$6$	$35$	No additional constraints.

Sample Input 1

1
1 4

Sample Output 1

99 23

Explanation for Sample Output 1

The integers $99$ and $23$ are coprime, i.e. their greatest common divisor is $1$. We have $\lfloor \frac{99}{23}\rfloor =4$, thus $R(99,23)=R(4,23)=R(23,4)$. Then $\lfloor \frac{23}{4}\rfloor =5$, so $R(23,4)=R(5,4)=R(1,4)=R(4,1)=4$.

Sample Input 2

2
3 2
5 5

Sample Output 2

9 39
5 5

Explanation for Sample Output 2

For the first test case, $gcd(9,39)=3$ and $R(9,39)=2$.

For the second test case, $gcd(5,5)=5$ and $R(5,5)=5$.