Anton has a positive integer nn, however, it quite looks like a mess, so he wants to make it beautiful after kk swaps of digits. 
Let the decimal representation of nn as (x1x2⋯xm)10(x1x2⋯xm)10 satisfying that 1≤x1≤91≤x1≤9, 0≤xi≤90≤xi≤9 (2≤i≤m)(2≤i≤m), which means n=∑mi=1xi10m−in=∑i=1mxi10m−i. In each swap, Anton can select two digits xixi and xjxj (1≤i≤j≤m)(1≤i≤j≤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 kk swaps?

Input

The first line contains one integer TT, indicating the number of test cases. 
Each of the following TT lines describes a test case and contains two space-separated integers nn and kk. 
1≤T≤1001≤T≤100, 1≤n,k≤1091≤n,k≤109. 

Output

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

Sample Input

5
12 1
213 2
998244353 1
998244353 2
998244353 3

Sample Output

12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332

 

大意就是给你一个数n，求在最多k次得交换下，能够得到的最大的数和最小得数是多少；一个数，假设他的k大于等于n得位数-1，那么不用遍历，k此后肯定是这种情况下这些数直接最小（大）排列所得的数，假设不是的话，那么你遍历一次最多的复杂度也就是10！这个，不会大于400w次遍历得，而且开的2.5s得时间，足够了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int maxn, minn, k, l, cnt = 0;
int readd(char n[20]) {
	int sum = 0, nz = strlen(n);
	for (int s = 0; s <nz; s++) {
		sum *= 10; sum += n[s] - '0';
	}
	return sum;
}
void bfs(char n[20], int step, int sum) {
	//cout << n << endl;
	if (sum == k || step == l-1) {
		int u = readd(n); minn = min(u, minn); maxn = max(maxn, u); ; return;
	}
	int u = readd(n);
	minn = min(u, minn); maxn = max(maxn, u);
	for (int s = step+1; s < l; s++) {
		if (step == 0 && n[s] == '0') continue;
		swap(n[step], n[s]);
		bfs(n, step + 1, sum + 1);
		swap(n[step], n[s]);
	}
	bfs(n, step + 1, sum);
	return;
}
int ***_max(char n[20]) {
	int nz = strlen(n);
	for (int s = 0; s < nz; s++) {
		int maxn = -1, wei = -1;
		for (int w = s + 1; w < nz; w++) {
			if (maxn < n[w] - '0') {
				maxn = n[w] - '0'; wei = w;
			}
		}
		if (maxn > n[s] - '0') {
			swap(n[s], n[wei]);
		}
	}
	return readd(n);
}
int ***_min(char n[20]) {
	int nz = strlen(n);
	for (int s = 0; s < nz; s++) {
		int minn = 0x3f3f3f3f, wei = -1;
		for (int w = s + 1; w < nz; w++) {
			if (minn > n[w] - '0' && !(s == 0 && n[w] == '0')) {
				minn = n[w] - '0'; wei = w;
			}
		}
		if (minn < n[s] - '0') {
			swap(n[s], n[wei]);
		}
	}
	return readd(n);
}
int main() {
	int te; char n[20];
	scanf("%d", &te);
	while (te--) {
		scanf("%s%d", n, &k);
		maxn = -1; minn = 0x3f3f3f3f;
		l = strlen(n);
		if (k >=  l- 1) {
			maxn = ***_max(n);
			minn = ***_min(n);
		}
		else bfs(n, 0, 0);
		printf("%d %d\n", minn, maxn);
	}
}