WA on#2

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,K;
string s;
int dp[N][21],pos[N][21],lg[N];
bool vis[N];
void build()
{
	lg[0]=-1;
	for(int i=1;i<=n;++i)
	{
		dp[i][0]=s[i]^48;
		pos[i][0]=i;
		lg[i]=lg[i/2]+1;
	}
	for(int j=1;j<=20;++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			if(dp[i][j-1]<=dp[i+(1<<j-1)][j-1])
			{
				dp[i][j]=dp[i][j-1];
				pos[i][j]=pos[i][j-1];
			}
			else
			{
				dp[i][j]=dp[i+(1<<j-1)][j-1];
				pos[i][j]=pos[i+(1<<j-1)][j-1];
			}
}
int query(int l,int r)
{
	int k=lg[r-l+1];
	if(dp[l][k]<=dp[r-(1<<k)+1][k])
		return pos[l][k];
	else
		return pos[r-(1<<k)+1][k];
}
void solve()
{
	memset(vis,0,sizeof vis);
	cin>>s>>K;
	n=s.size();
	s="#"+s;
	build();
	if(!K)
	{
		cout<<s.substr(1)<<'\n';
		return ;
	}
	if(K==n-1)
	{
		int p=-1;
		for(int i=1;i<=n;++i)
			if(s[i]!='0'&&(p==-1||s[i]<s[p]))
				p=i;
		cout<<s[p]<<'\n';
		return ;
	}
	int lst=-1;
	for(int i=1;i<=K+1;++i)
		if((lst==-1||s[i]<s[lst])&&(s[i]^48))
			lst=i;
	vis[lst]=1;
	K-=lst-1;
	while(K>=0&&lst<n)
	{
		int r=min(n,lst+K+1),l=min(n,lst+1),p=query(l,r);
		vis[p]=1;
		K-=p-l;
		lst=p;
	}
	for(int i=1;i<=n;++i)
		if(vis[i])
			cout<<s[i];
	cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	for(cin>>T;T;--T)
		solve();
}//fkec