Anton has a positive integer $n$, however, it quite looks like a mess, so he wants to make it beautiful after $k$ swaps of digits.
Let the decimal representation of $n$ as $(x_1 x_2 \cdots x_m)_{10}$ satisfying that $1 \leq x_1 \leq 9$, $0 \leq x_i \leq 9$ $(2 \leq i \leq m)$, which means $n = \sum_{i = 1}^{m}{x_i 10^{m - i}}$. In each swap, Anton can select two digits $x_i$ and $x_j$ $(1 \leq i \leq j \leq m)$ and then swap them if the integer after this swap has no leading zero.
Could you please tell him the minimum integer and the maximum integer he can obtain after $k$ swaps?

The first line contains one integer $T$, indicating the number of test cases.
Each of the following $T$ lines describes a test case and contains two space-separated integers $n$ and $k$.
$1 \leq T \leq 100$, $1 \leq n, k \leq 10^9$.

For each test case, print in one line the minimum integer and the maximum integer which are separated by one space.