409152: GYM103447 D Math master

Tang Keke is good at math. She knows how to simplify fractions very well. Even greater, she invented a simplifying method by herself!

The method is to choose some digits which appear in both the top and the bottom and erase them on both sides while keeping the fraction value unchanged. The digits are the same, so they can reduce each other. Sounds very logical, right?

The method may produce multiple simplified results and the one with the least top number is called the most simplified form. Keke prepared some fractions and is going to test if you can get the most simplified form.

Note that the chosen digits form a multiset, you can see the examples for more details.

The first line contains an integer $$$n\,(1 \le n \le 10)$$$, denoting the number of fractions.

Each of the next $$$n$$$ lines contains two integer $$$p,q\,(0 < p, q < 2^{63})$$$, denoting the fraction $$$\frac{p}{q}$$$.

For each fraction, output two integers $$$x,y$$$ in one line, indicating the most simplified form of the corresponding fraction is $$$\frac{x}{y}$$$.

Notice: if there are some leading zeros after removal, you can ignore them and output the normal number. For example, if you get 007/123 finally, then you should output "7 123" instead of "007 123".

4
163 326
326 163
1000 1000
2232 162936

1 2
2 1
1 1
232 16936

• For the first and the second case, the erased digit multisets are both $$$\{3,6\}$$$.
• For the third case, the erased digit multiset is $$$\{0,0,0\}$$$.
• For the fourth case, the erased digit multiset is $$$\{2\}$$$.