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 , he marks them as so that . Then the numbers are erased and he writes on the sand, and repeats the process. When one of the two numbers becomes , the other is the results of his algorithm.

Formally, if and are positive integers, the result of Edicul's algorithm is:

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 and , find positive integers and such that their greatest common divisor is , and the result of Edicul's algorithm is .

#### Input

The first line contains a single integer – the number of independent test cases.

Each of the following lines contains two positive integers and .

#### Output

Output lines in total. For the -th testcase, output positive integers and such that and .

The numbers in the output must not be larger than . 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.

#### Scoring

In all subtasks, and .

Subtask | Score | Constraints |
---|---|---|

No additional constraints. |

#### Sample Input 1

```
1
1 4
```

#### Sample Output 1

`99 23`

#### Explanation for Sample Output 1

The integers and are coprime, i.e. their greatest common divisor is . We have , thus . Then , so .

#### Sample Input 2

```
2
3 2
5 5
```

#### Sample Output 2

```
9 39
5 5
```

#### Explanation for Sample Output 2

For the first testcase, and .

For the second testcase, and .

## Comments