Untitled

#include <iostream>

using namespace std;
int TC;
int d[10000001],s[10000001];
int n,k,m;
char nn[10];
bool ok;
int min(int x, int y)
{
	if(x>y)return y;
	return x;
}
int a[8];
void swap(int &x, int &y)
{
	int u=x;
	x=y;
	y=u;
}
int swap1(int x, int vt1,int vt2)
{
	int cnt=0;
	while(x)
	{
		a[++cnt]=x%10;
		x/=10;
	}
	while(cnt<m)
	{
		a[++cnt]=0;
	}
	for(int i=1;i<=cnt/2;i++)swap(a[i],a[cnt-i+1]);
	swap(a[vt1],a[vt2]);
	int ans=0;
	for(int i=1;i<=cnt;i++)ans=ans*10+a[i];
	return ans;
}
int len(int x)
{
	int ans=0;
	while(x)
	{
		ans++;
		x/=10;
	}
	return ans;
}
int dd[10];

int size(char* c) {
	int ans=0;
	while(c[ans]!=0)ans++;
	return ans;
}

int stoi(char* c){
	int ans=0;
	int id=0;
	while(c[id]!=0)
	{
		ans=ans*10+c[id]-'0';
		id++;
	}
	return ans;
}
void doc(int tc)
{
	ok=false;
	int ans=0;
	cin>>nn>>k;
	m=size(nn);
	n=stoi(nn);
	for(int i=0;i<=9;i++)dd[i]=0;

	for(int i=0;i<m;i++)
	{
		dd[nn[i]-'0']++;
		if(dd[nn[i]-'0']>=2)ok=true;
	}

	//cout<<n<<" "<<k<<"\n";
	for(int i=1;i<=min(n*10,10000000);i++)d[i]=0;
	int dau=1,cuoi=0;
	s[++cuoi]=n;
	d[n]=1;
	while(cuoi>=dau)
	{
		int x=s[dau++];
		if((k+1-d[x])%2==0&&ans<x)ans=x;
		if(ok&&ans<x)ans=x;
		
		//cout<<x<<" - "<<leng<<"\n";
		for(int i=1;i<=m;i++)
			for(int j=1;j<=m;j++)
			{
				int y=swap1(x,i,j);
				if(d[y]==0&&d[x]+1<=k+1)
					{
						d[y]=d[x]+1;
						s[++cuoi]=y;
						//cout<<"them "<<y<<"\n";
				}
			}
	}
	
	cout<<"Case #"<<tc<<"\n";
	cout<<ans<<"\n";

}

int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	//cout<<swap1(123,1,3)<<"\n";
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
       doc(tc);
	}
    return 0;
}