#include<bits/stdc++.h>
#define lb(x) (x&-x)
#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs (ls|1)
#define int long long
#define pii pair<int,int>
using namespace std;
const int maxn = 2e6+10;
struct INT{
	static constexpr int D = 100000, Dc = log10(D);
	int a[maxn],n; //[1...n]
	void clear() {
		memset(a+1,0,(n)*sizeof a[0]);
		n=0;
	}
	void add_equal(INT const&rhs) {
		// infun(*this,rhs);
		int m = rhs.n; auto&b=rhs.a;
		// deb(n,m,a[0],a[1],a[2],a[3],a[4],a[5]);
		// deb(b[1],b[2],b[3],b[4]);
		int i = 1,gg=0;
		for(;i <= max(n,m) || a[i+1];++i) {
			a[gg=i] += b[i];
			if(a[i] >= D) a[i] -= D, ++a[gg=i+1];
		}n=gg;
		// deb(i);

		// debf(a[1],a[2],a[3],a[4]);

	}
	void operator=(INT const&rhs){
		clear();
		n=rhs.n;
		memcpy(a+1,rhs.a+1,n*sizeof a[0]);
		// debf(a[1],a[2],a[3],a[4]);

	}
	bool operator<(INT const&rhs)const{
		int m = rhs.n; auto&b=rhs.a;
		if(n != m) return n < m;
		for(int i = n;i;--i)
			if(a[i]!=b[i]) return a[i] < b[i];
		return 0;
	}
	friend ostream&operator<<(ostream&cout,INT const&va) {
		int n=va.n; auto&a=va.a;
		cout<<a[n];
		while(--n>0)cout<<setw(Dc)<<setfill('0')<<a[n];
		return cout.clear(),cout;
	}
	void setval(char* beg,char* end) {
		clear();
		n = 1; int W=1;
		while(end!=beg) {
			--end;
			if(W >= D)++n,W=1;
			(a[n])+=W*(*end&15);W*=10;
		}
		// debf(a[1],a[2],a[3],a[4]);
	}
	// void setval(auto rang){setval(rang.begin(),rang.end());}
}ans,res,cur;
int T;
int n,k;
char a[maxn];
int la;
int ds[maxn];
void cal() {
	res.clear();//, cur.clear();
	for(int i = 0;i <= k;++i) {
		// deb(i,g);
		// deb(res);
		cur.setval(a+ds[i]+1,a+ds[i+1]+1);
		// deb(res,cur);
		res.add_equal(cur);
		// deb(res);
	}
	// assert(g == n);
	// deb(res);
	if(res < ans || !ans.n) ans = res;
}
void dfs(int d,int pre) {
	if(pre <= 0)return;
	// infun(d,pre);
	if(d == k+2 && ds[d-1] == n) {
		cal();
		return;
	}
	if(d > k+1) return;
	ds[d]=ds[d-1]+pre;
	dfs(d+1,pre);
	ds[d]=ds[d-1]+pre-1;
	dfs(d+1,pre-1);
	ds[d]=ds[d-1]+pre+1;
	dfs(d+1,pre+1);
}
void sol() {
	ans.clear();
	cin>>n>>k>>(char(&)[maxn])a[1];
	la = n/(k+1);
	for(int a=sqrt(n)/3;a <= la*10;++a) dfs(1,a);
	cout<<ans<<'\n';
}
signed main() {
	// freopen("E.in","r",stdin);
	// freopen("E.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;while(T--)sol();
}