Anton 有一个正整数 $n$，但他觉得这个数看起来很乱，所以他想通过 $k$ 次数字交换让它变得“漂亮”。

设 $n$ 的十进制表示为 $(x_1 x_2 \dots x_m)_{10}$，满足 $1 \le x_1 \le 9$ 且 $0 \le x_i \le 9$ ($2 \le i \le m$)，即 $n = \sum_{i=1}^m x_i 10^{m-i}$。在每次交换中，Anton 可以选择两个位置 $i$ 和 $j$ ($1 \le i < j \le m$)，并交换这两个位置上的数字，前提是交换后的整数没有前导零。

请你告诉他，在进行 $k$ 次交换后，他能得到的最小整数和最大整数分别是多少？

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来的 $T$ 行，每行描述一个测试用例，包含两个用空格分隔的整数 $n$ 和 $k$。 $1 \le T \le 100, 1 \le n, k \le 10^9$。

输出格式

对于每个测试用例，输出一行，包含两个由空格分隔的整数，分别表示最小整数和最大整数。

样例

样例输入 1

5
12 1
213 2
998244353 1
998244353 2
998244353 3

样例输出 1

12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332