#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#pragma GCC optimize(2) 

using namespace std;

char Mid[200500];
int Map[200500];

int Ans[200500];
int Sum[200500];

int MM =0;

int Anspoint = 2147483647;
int Sumpoint = 0;

void ADD(int p,int n)
{
	for(int i=1;i<=n;i++)
	{
		Sum[i] += Map[p+i];
	}
	Sumpoint = max(Sumpoint,n);
}

void clearSum()
{
	int flag = Sumpoint;
	for(int i=1;i<=Sumpoint;i++)
	{
		if(Ans[i]>=10)
			Sumpoint = max(Sumpoint,i+1);
		Sum[i+1] += Sum[i]/10;
		Sum[i] %= 10;
	}

}

void change()
{
	Anspoint = Sumpoint;
	for(int i=1;i<=Sumpoint;i++)
	{
		Ans[i] = Sum[i];
	}
}

void updateAns()
{
	if(Anspoint>Sumpoint)
	{
		change();
	}
	else if(Anspoint==Sumpoint)
	{
		for(int i=Anspoint;i>=1;i--)
		{
			if(Ans[i]>Sum[i])
			{
				change();
				break;
			}
			else if(Ans[i] < Sum[i])
				break;
		}
	}
}

int checki(int range,int n,int k,int avg)
{	
	int Cek[10];
	for(int i=1;i<k;i++)
	{
		if(range%3 == 2)
			Cek[i] = -1;
		else if(range%3 == 1)
			Cek[i] = 1;
		else
		 	Cek[i] = 0;
		range/=3;
	}
	
	Cek[0] = 0;
	
	for(int i=1;i<k;i++)
	{
		Cek[i] = Cek[i-1] + Cek[i];
	}
	
	int Sum = 0; 
	
	for(int i=1;i<k;i++)
	{
		Sum+=Cek[i];
	}
	
	for(int i=avg-5;i<=avg+5;i++)
	{
		if(i*k+Sum == n)
		{
			return i;
		}
	}
	return 0;
}

int main()
{
	int T;
	scanf("%d",&T);
	int MM = 0;
	for(int L=1;L<=T;L++)
	{
		int n,k;
		Anspoint = 2147483647;
		scanf("%d%d",&n,&k);
		k+=1;	
		scanf("%s",Mid);
		int len = strlen(Mid);
		for(int i=len;i>=1;i--)
		{
			Map[i] = Mid[len-i] - '0';
		}
		int avg = n/k;
		int type = pow(3,k-1);
		type -= 1;

		int LAST = avg-2;
		
		for(int i = type;i>=0;i--)
		{
			int Last = checki(i,n,k,avg);
			if(!Last)
			{
				continue;
			}
		
			int MID = i;
			int Sumn = 0;
			Sumpoint = 0;
			for(int i=1;i<=avg+10;i++)
			{
				Sum[i] = 0;
			}
			int c=1;
			if(Last < 1)
			{
				continue;
			}
			ADD(Sumn,Last);
			Sumn+=Last;
			int last = Last;
			for(int j=2;j<=k;j++)
			{
				if(MID%3 == 2)
				{
					if(last-1 <= 0)
					{
						break;
					}
					
					ADD(Sumn,last-1);
					Sumn+=last-1;
					last -=1;
				}
				else if(MID%3 == 1)
				{
					ADD(Sumn,last+1);
					Sumn+=last+1;
					last +=1;
				}
				else
				{
					ADD(Sumn,last);
					Sumn+=last;
				}
				MID/=3;
			}
			if(Sumn == n)
			{
				clearSum();
				updateAns();
			}
		}

		for(int i=1;i<=Anspoint;i++)
		{
			if(Ans[i]>=10)
				Anspoint = max(Anspoint,i+1);
			Ans[i+1] += Ans[i]/10;
			Ans[i] %= 10;
		}

		for(int i=Anspoint;i>=1;i--)
		{
			putchar('0'+Ans[i]);
			//printf("%d",Ans[i]);
		}
		printf("\n");
		
	}
}

/*


1
3 1
643

2
2 1
42



20
10 2
2156345972

20
14 3
32154512561264

20
14 6
12345678910354

10
10 3
1111111111

73745151612994128663659691951

100
119 4
74557467972773121782538891362827481768912897991754711869314352623359371753878285451828757473745151612994128663659691951



119 4
745574679727731217825388913628
274817689128979917547118693143
526233593717538782854518287574
73745151612994128663659691951

2411812927269438997564718


*/