#include <bits/stdc++.h>
using namespace std;
using poly=vector<int>;
poly operator+(poly a,poly b){
    poly ans;
    int sa=a.size(),sb=b.size();
    ans.resize(max(sa,sb));
    int t=0;
    for(int i=0;i<max(sa,sb);i++){
        if(i<sa)    t+=a[i];
        if(i<sb)    t+=b[i];
        ans[i]=t%10, t/=10;
    }
    while(t)    ans.push_back(t%10),t/=10;
    return ans;
}
bool operator<(poly a,poly b){
    if(a.size()!=b.size())  return a.size()<b.size();
    int sz=a.size();
    for(int i=sz-1;i>=0;i--)    if(a[i]!=b[i])  return a[i]<b[i];
    return true;
}

void solve(void) {
    int n,k;
    cin>>n>>k;
    vector<int> w;
    for(int i=0;i<n;i++){
        char c;
        cin>>c;
        w.push_back(c-'0');
    }
    int hap=n/(k+1);
    vector<vector<poly>> maxn(n+1,vector<poly>(k+1));
    auto dfs=[&](auto self,int u,int sum)->poly {
        if(u==k+1)  return poly(1,0);
        if(sum==n)    return poly(0);
        if(!maxn[sum][u].empty())   return maxn[sum][u];
        int lo=max(sum+1,sum+hap-2),ro=min(n,sum+hap+2);
        if(u==k)    lo=ro=n;
        poly res;
        for(int i=lo;i<=ro;i++){
            if(i>n)   break;
            poly nxt=self(self,u+1,i);
            if(!nxt.empty()){
                poly now(i-sum);
                for(int j=i-1;j>=sum;j--) now[i-j-1]=w[j];
                // cerr<<"?"<<sum<<' '<<i-1<<'\n';
                // for(auto i:now) cerr<<i;
                // cerr<<' ';
                // for(auto i:nxt) cerr<<i;
                // cerr<<'\n';
                now=now+nxt;
                if(res.empty()||now<res)    res=now;
            }
        }
        return maxn[sum][u]=res;
    };
    poly ans=dfs(dfs,0,0);
    reverse(ans.begin(),ans.end());
    for(auto i:ans) cout<<i;
    cout<<'\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int _ = 1;
    cin>>_;
    while (_--) solve();

    // cerr << clock() * 1000. / CLOCKS_PER_SEC << endl;

    return 0;
}
/*
2
8 1
45455151
2 1
42
*/
/*
1
8 1
45455151
*/
/*
1
2 1
42

*/