#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+5;
#define TT 10000000000000000ll
int T,n,k,num_duan,num_chang,duan,ok,cnt,cho[101],calc;
int anss[N][11];
char str[N];
inline int read(){                                                 
    int al=0,fh=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
    if(ch=='-')
    al=-1;
    ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
    al=al*10+ch-'0';
    ch=getchar();
    }
    return al*fh;
}
int NN;
struct Big_int{
	int a[N/16+15];
    int len;
    Big_int(){len=0;memset(a,0,sizeof(int)*NN);}
    Big_int(char *s,int Len){
        int L=Len,yu=(L-1)%16+1;len=L=(L+15)/16;
        for (int i=0;i<yu;i++) a[L]=a[L]*10+s[i]-'0';
        for (int i=yu;i<Len;i+=16){
            int x=0;
            for (int j=i;j<i+16;j++) x=x*10+s[j]-'0';
            a[--L]=x;
        }
    }
	Big_int& operator =(const Big_int&b){
		memcpy(a,b.a,sizeof(int)*NN);
		len=b.len;
		return *this;
	}
	void Zhuan(char *s,int Len){
		memset(a,0,sizeof(int)*NN);
        int L=Len,yu=(L-1)%16+1;len=L=(L+15)/16;
        for (int i=0;i<yu;i++) a[L]=a[L]*10+s[i]-'0';
        for (int i=yu;i<Len;i+=16){
            int x=0;
            for (int j=i;j<i+16;j++) x=x*10+s[j]-'0';
            a[--L]=x;
        }
    }
    Big_int operator +(const Big_int&b){
        Big_int c;
        c.len=max(len,b.len);
        for (int i=1;i<=c.len;i++){
            c.a[i]+=a[i]+b.a[i];
            c.a[i+1]+=c.a[i]/TT;
            c.a[i]%=TT;
        }
        if (c.a[c.len+1]) c.len++;
        return c;
    }
	Big_int&operator +=(const Big_int&b){
        len=max(len,b.len);
        for (int i=1;i<=len;i++){
            a[i]+=b.a[i];
            a[i+1]+=a[i]/TT;
            a[i]%=TT;
        }
        if (a[len+1]) len++;
        return *this;
    }
    void print(){
        printf("%lld",a[len]);
        for (int i=len-1;i;i--) printf("%016lld",a[i]);
        printf("\n");
    }
}o,ans;
void zhuan(int l,int r){
    o.Zhuan(str+l,r-l+1);
}
bool cmp(Big_int s,Big_int st){
    if(s.len!=st.len) return s.len<st.len;
    for(int i=s.len;i>=1;i--){
        if(s.a[i]!=st.a[i]) return s.a[i]<st.a[i];
    }
    return false;
}
void dfs(int now,int al,int minn,int maxx){
    calc++;
    if(maxx-minn>=3){
        return ;
    }
    if(now==k+2){
        if(al==n){
            cnt++;
            for(int i=1;i<=k+1;i++){
                anss[cnt][i]=cho[i];
            }
            return;
        }
        else {
            return;
        }
    }
    for(int i=max(cho[now-1]-1,max(1ll,duan-2));i<=min(min(n,duan+2),cho[now-1]+1);i++){
        cho[now]=i;
        dfs(now+1,al+i,min(minn,cho[now]),max(maxx,cho[now]));    
    }
}
signed main(){
    T=read();
    for(int yyc=1;yyc<=T;yyc++){
        n=read();
        k=read();
        ok=0;
        scanf("%s",str);
        duan=n/(k+1);NN=duan/16+10;
        cnt=0;
        cho[1]=duan;
        if(cho[1]<=n&&cho[1]>=1)
        dfs(2,cho[1],cho[1],cho[1]);
        cho[1]=duan+1;
        if(cho[1]<=n&&cho[1]>=1)
        dfs(2,cho[1],cho[1],cho[1]);
        cho[1]=duan+2;
        if(cho[1]<=n&&cho[1]>=1)
        dfs(2,cho[1],cho[1],cho[1]);
        cho[1]=duan-1;
        if(cho[1]<=n&&cho[1]>=1)
        dfs(2,cho[1],cho[1],cho[1]);
        cho[1]=duan-2;
        if(cho[1]<=n&&cho[1]>=1)
        dfs(2,cho[1],cho[1],cho[1]);
        Big_int maxx=Big_int();
        int ok=0;
        for(int i=1;i<=cnt;i++){
            ans=Big_int();
            int now=0;
            for(int j=1;j<=k+1;j++){
                zhuan(now,now+anss[i][j]-1);
                ans+=o;
                now+=anss[i][j];
            }
            if(ok==0||cmp(maxx,ans)==0){
                ok=1;
                maxx=ans;
            }
        }
        maxx.print();
    }
}