#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <queue>
#include <numeric>
#include <cstring>
#define f(x, a, b) for (int x = a; x < b; x++)
#define fm(x, a, b) for (int x = a; x > b; x--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
using namespace std;
typedef unsigned long long ll;
typedef long long int li;
const li mod=1e9+7;
const int x1 = 100;
struct bignum {
    vector<int> dig;
    int val = x1;

    bignum(int v = x1) {
        dig.resize(v,0);
        val=v;;
    }
    bignum(string &s, int l, int r) {
        // dig.resize(r-l);
        // val = r-l;
        dig.resize(val,0);
        assert(l<r);
        assert(r<=sz(s) && l>=0);
        int j=0;
        fm(i,r-1,l-1) {
            dig[j]=s[i]-'0';
            j++;
        }
    }
    void add(bignum &b) {
        int carry=0;
        f(i,0,val) {
            dig[i] += b.dig[i]+carry;
            if (dig[i]>=10) {
                dig[i]-=10;
                carry=1;
            }
            else
                carry=0;
        }
    }
    bool greater(bignum &b) {
        fm(i,val-1,-1) {
            if (dig[i]>b.dig[i])
                return true;
            if (dig[i]<b.dig[i])
                return false;
        }
        return false;
    }
    void print() {
        int i=val-1;
        while (i>=0 && dig[i]==0)
            i--;
        if (i==-1)
            cout <<0;
        else {
            fm(j,i,-1)
                cout <<dig[j];
        }
        cout <<"\n";
    }
    
};



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >>t;
    while(t--) {
        int n,k;
        cin >>n>>k;
        k++;
        string s;
        cin >>s;
        int bs = n+10;
        vector<bignum> dp(n+1,bignum(0));
        int l1 = max(n/k-2*(k-1)-1,1);
        int r1 = min(n/k+3,n);
        f(i,l1,r1) {
            dp[i] = bignum(s,0,i);
        }
        pair<int,int> last = mp(l1,r1);
        f(i,2,k) {
            int lc = max((n/k)*i-2*(k-i)-1,1);
            int rc = min((n/k)*i+2*i+1,n);
            vector<bignum> dp2(rc-lc,bignum(0));
            f(j,lc,rc) {
                f(j2,last.first,min(last.second,j)) {
                    bignum temp = bignum(s,j2,j);
                    temp.add(dp[j2]);
                    if (dp2[j-lc].val == 0 || !temp.greater(dp2[j-lc])) {
                        dp2[j-lc] = temp;
                    }
                }
            }
            f(j,lc,rc) {
                dp[j] = dp2[j-lc];
            }
            last = mp(lc,rc);
        }
        f(i,last.first,last.second) {
            bignum temp = bignum(s,i,n);
            temp.add(dp[i]);
            if (dp[n].val == 0 || !temp.greater(dp[n])) {
                dp[n] = temp;
            }
        }
        dp[n].print();
    }
}