Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

C. Long Multiplication
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers x and y of the same length, consisting of digits from 1 to 9.

You can perform the following operation any number of times (possibly zero): swap the i-th digit in x and the i-th digit in y.

For example, if x=73 and y=31, you can swap the 2-nd digits and get x=71 and y=33.

Your task is to maximize the product of x and y using the aforementioned operation any number of times. If there are multiple answers, print any of them.

Input

The first line contains a single integer t (1t1000) — the number of test cases.

The first line of each test case contains a single integer x (1x<10100).

The second line of each test case contains a single integer y (1y<10100).

Additional constraint on input: the integers x and y consist only of digits from 1 to 9.

Output

For each test case, print two lines — the first line should contain the number x after performing the operations; similarly, the second line should contain the number y after performing the operations. If there are multiple answers, print any of them.

Example
Input
3
73
31
2
5
3516
3982
Output
71
33
5
2
3912
3586