시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

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_1x_2 \dots x_m)_{10}\) satisfying that \(1 \le x_1 \le 9, 0 \le x_i \le 9 (2 \le i \le m)\), which means \(n = \sum_{i=1}^{m}{x_i10^{m−i}}\). In each swap, Anton can select two digits \(x_i\) and \(x_j\) (\(1 \le i \le j \le 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 \le T \le 100, 1 \le n, k \le 10^9\).

출력

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

예제 입력 1

5
12 1
213 2
998244353 1
998244353 2
998244353 3

예제 출력 1

12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332