Euclide

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:

~ R(a, b) = \begin{cases} R(b, a), & \text{if } a < b \\ R\left(\left\lfloor \frac{a}{b} \right\rfloor, b\right), & \text{if } a \ge b > 1 \\ a, & \text{if } a \ge 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

• 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 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 larget 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.

Examples

1
1 4

99 23

2
3 2
5 5

9 39
5 5