#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll e,ee,n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],siz,normalsize;
vector<ll> ans;
vector<ll> add(vector<ll> a,vector<ll> b)
{
    vector<ll> v;
    v.resize(max(a.size(),b.size())+1);
    ll i;
    for(i=0;i<a.size();i++)
        v[i]+=a[i];
    for(i=0;i<b.size();i++)
        v[i]+=b[i];
    for(i=0;i<v.size();i++)
    {
        if(v[i]>=10)
        {
            v[i+1]+=v[i]/10;
            v[i]%=10;
        }
    }
    return v;
}
vector<ll> interval(ll x,ll y)
{
    ll i,s=0;
    vector<ll> v;
    v.resize(y-x+1);
    for(i=y;i>=x;i--)
    {
        v[s]+=a[i];
        s++;
    }
    return v;
}
ll bigger(vector<ll> a,vector<ll> b)
{
    if(a.empty())
        return 1;
    if(b.empty())
        return 0;
    ll i;
    if(a.size()>b.size())
    {
        for(i=ll(a.size())-1;i>=b.size();i--)
        {
            if(a[i])
                return 1;
        }
    }
    if(b.size()>a.size())
    {
        for(i=ll(b.size())-1;i>=a.size();i--)
        {
            if(b[i])
                return 0;
        }
    }
        for(i=min(b.size(),a.size())-1;i>=0;i--)
        {
            if(a[i]<b[i])
                return 0;
            if(a[i]>b[i])
                return 1;
        }
        return 1;
}
void show(vector<ll> a)
{
    return;
    ll i;
    for(i=0;i<a.size();i++)
        printf("%lld ",a[ll(a.size())-1-i]);
    printf("\n");
}
vector<ll> f(ll x,ll y,ll z)
{
    if(z==0)
    {
       // printf("(%lld,%lld,%lld):",x,y,z);
        show(interval(x,y));
        return interval(x,y);
    }
    vector<ll> u;
    vector<ll> v1,v2,v3;
    if(normalsize>1&&(y-(x+normalsize-1)+1)>z-1)
    v1=add(f(x+normalsize-1,y,z-1),interval(x,x+normalsize-2));
   // printf("!(%lld)",v1.size());
    if(y-(x+normalsize)+1>z-1)
    {
        v2=add(f(x+normalsize,y,z-1),interval(x,x+normalsize-1));
    }
    if(y-(x+normalsize+1)+1>z-1)
    {
        v3=add(f(x+normalsize+1,y,z-1),interval(x,x+normalsize));
    }
    show(v1);
    show(v2);
    show(v3);
   // printf("?");
    if(bigger(v1,v2))
        {swap(v1,v2);
        //printf("(!)");
        }
   // show(v1);
    if(bigger(v1,v3))
        {swap(v3,v1);
       // printf("(?)");}
}
        //printf("(%lld,%lld,%lld):",x,y,z);
        show(v1);
    return v1;
}
int main()
{
    scanf("%lld",&e);
    for(ee=0;ee<e;ee++)
    {
        scanf("%lld %lld",&n,&k);
        siz=n/(k+1)+10;
        normalsize=(n+k)/(k+1);
       // printf("(%lld,%lld)\n",siz,normalsize);
        for(i=1;i<=n;i++)
        {
            scanf("%01lld",&a[i]);
        }
        //show(interval(5,8));
        ans=f(1,n,k);
        //printf("(%lld)",ans.size());
        x=0;
        for(i=ll(ans.size())-1;i>=0;i--)
        {
            if(ans[i])
                x=1;
            if(x==0)
                continue;
            printf("%lld",ans[i]);
        }
        printf("\n");
}
}