D. Daydreaming Strings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For João Braga, Calculus III is the easiest subject that he's ever studied, despite Mr. LV's greatest efforts. Because of this, he tends to drift off during class (as he doesn't need to study) and tries to distract himself with games he comes up with in his mind. One day he came up with a really exciting game: João Braga would randomly select two words from the blackboard and mess around with them. After selecting these two words, he would concatenate them and swap any two characters as he pleases. The game is considered successful if he's able to find the lexicographically smallest combination. Given these two strings $$$s$$$ and $$$t$$$, can you help João Braga find it?

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$.
  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter of $$$b$$$
Input

The first line contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$ — the number of test cases.

Each test case is one line and contains two strings, $$$(1 \leq |s|, |t| \leq 10^3)$$$ — the words that João Braga chose, all of which only contain lowercase Latin letters.

Output

For each test case, output a single string — the lexicographically smallest combination.

Example
Input
2
ime brasil
calvao decria
Output
abeiilmrs
aaaccdeilorv