#include<bits/stdc++.h>
using namespace std;

string str;
int a[500005];
int del,t;
int lg[500005];
pair<int,int> st[500005][20];
void LOG(){
	lg[0]=-1;
	for(int i=1;i<=500005;i++){
		lg[i]=lg[i>>1]+1;
	}
}
void stmin(string str){//ST表 
	for(int s=0;s<str.size();s++){
		st[s][0]={str[s]-'0',s};
	}
	for(int k=1;k<=lg[str.size()];k++){
		for(int s=0;s+(1<<k)-1<str.size();s++){
			if(st[s][k-1].first<=st[s+(1<<(k-1))][k-1].first){
				st[s][k]=st[s][k-1];
			}
			else{
				st[s][k]=st[s+(1<<(k-1))][k-1];
			}
			//cerr<<s<<' '<<k<<' '<<st[s][k].first<<' '<<st[s][k].second<<endl;
		}
	}
}
int minn(int l,int r){//求区间最小值 
	int k=lg[r-l+1];
	//cerr<<k<<' '<<l<<' '<<r<<' '<<endl;
	if(st[l][k].first<=st[r-(1<<k)+1][k].first){
		return st[l][k].first;
	}
	else{
		return st[r-(1<<k)+1][k].first;
	}
}
int now(int l,int r){//求最小值所对应位置 
	int k=lg[r-l+1];
	if(st[l][k].first<=st[r-(1<<k)+1][k].first){
		return st[l][k].second;
	}
	else{
		return st[r-(1<<k)+1][k].second;
	}
}
int main(){
	cin>>t;
	LOG();
	while(t--){
	cin>>str>>del;
	int last=str.size()-del-1;
	stmin(str);
	int pre=-1,i=0;
	for(;last>=0;last--,i++){
		a[i]=minn(pre+1,str.size()-last-1);
		pre=now(pre+1,str.size()-last-1);
	}
	int j=0;
	for(;j<i;j++){
		if(a[j]!=0){
			break;
		}
	}
	int flag=0;
	for(;j<i;j++){
		flag=1;
		cout<<a[j];
	}
	if(flag==0){
		cout<<0;
	}
	cout<<endl;
	}
}