Beautiful Now

Time limit2sMemory limit512 MB

Summary

Given an integer n and a swap budget k, find the smallest and largest numbers reachable by swapping digit positions, where no intermediate or final number may have a leading zero.

Level: Medium7 of 10
Topics: Greedy, Brute force, DFS, String
Solved: No attempts yet

Problem

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?

Input

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).

Output

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

Examples1

Example 1

Input

5
12 1
213 2
998244353 1
998244353 2
998244353 3

Expected output

12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332