#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
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++)
	{
		Sum[i+1] += Sum[i]/10;
		Sum[i] %= 10; 
	}
	while(Sum[flag]>10)
	{
		Sum[flag+1] = Sum[flag]/10;
		Sum[flag]%=10;
		flag+=1;
		Sumpoint = flag;
	}

}

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 begin,int ANS,int k)
{
	int SUM = begin;
	int last = begin;
	for(int i=2;i<=k;i++)
	{
		if(range%3 == 2)
		{
			SUM+=last-1;
			last-=1;
		}
		else if(range%3 == 1)
		{
			SUM+=last+1;
			last+=1;
		}
		else
		{
			SUM+=last;
		}
	}
	if(SUM == ANS)
		return 1;
	else
		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--)
		{
			for(int j=1,Last=LAST;j<=5;j++,Last+=1)
			{	
				
				if(!checki(i,Last,n,k))
				{
					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=Anspoint;i>=1;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


*/