#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

vector<int> add(const vector<int> &a,const vector<int> &b) {
    if(a.size() < b.size()) return add(b, a);
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size(); i ++ ) {
        t += a[i];
        if(b.size() > i) t += b[i];
        c.push_back(t % 100000000)  ;
        t /= 100000000;
    }
    if(t) c.push_back(t);
    return c;
}

void print(const vector<int> &c) {
    for(int i = c.size() - 1; i >= 0; i -- ){
        if(i != c.size() - 1) cout << setw(8) << setfill('0') << c[i];
        else cout << c[i];
        // cout << c[i];
    }
        
    cout << '\n';
}

bool cmp(const vector<int> &a, const vector<int> &b) {
    if(a.size() > b.size()) return true;
    else if(a.size() < b.size()) return false;
    for(int i = a.size() - 1; i >= 0; i -- ) {
        if(a[i] != b[i]) {
            return a[i] > b[i];
        }
    }
    return false;
}

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int has = n / (k + 1) - 1;
    int other = n % (k + 1) + k + 1;
    vector<int> ans;
    for(int i = 0; i < (1 << 2 * (k + 1)); i ++ ) {
        int cnt = 0;
        bool er = 0;
        for(int j = 0; j < 2 * (k + 1); j += 2) {
            int tmp = 0;
            if((i >> j) & 1) {
                cnt ++ ;
                tmp += 2;
            }
            if((i >> (j + 1)) & 1) {
                if((i >> j) & 1)cnt ++;
                tmp += 1;
            }
            if(tmp == 1) {
                er = 1;
                break;
            }
            if(has == 0 && tmp == 0){
                er = 1;
            }
        }
        if(er) continue;
        vector<int> c;
        if(cnt == other) {
            int now = 0;
            for(int j = 0; j < 2 * (k + 1); j += 2) {
                vector<int> a;
                for(int z = now + has + ((i >> j) & 1) + ((i >> j + 1) & 1) - 1; z >= now; z -= 8) {
                    int tmp = 0;
                    int p = 1;
                    for(int k = 0; k < 8; k ++ ){
                        if(z - k >= now)tmp += (s[z - k] - '0') * p;
                        p *= 10;
                    }
                    a.push_back(tmp);
                    // assert(z < n);
                    // a.push_back(s[z] - '0');
                    // cout << z << ' ' << tmp << '\n';
                }
                // print(a);
                now = now + has + ((i >> j) & 1) + ((i >> j + 1) & 1);
                c = add(c, a);
            }
            // print(c);
            // cout << '\n';
            if(ans.size() == 0) {
                ans = c;
            } else {
                if(cmp(ans, c)) {
                    ans = c;
                }
            }
        }
    }
    has ++;
    other -= k + 1;
    for(int i = 0; i < (1 << 2 * (k + 1)); i ++ ) {
        int cnt = 0;
        bool er = 0;
        for(int j = 0; j < 2 * (k + 1); j += 2) {
            int tmp = 0;
            if((i >> j) & 1) {
                cnt ++ ;
                tmp += 2;
            }
            if((i >> (j + 1)) & 1) {
                if((i >> j) & 1)cnt ++;
                tmp += 1;
            }
            if(tmp == 1) {
                er = 1;
                break;
            }
            if(has == 0 && tmp == 0){
                er = 1;
            }
        }
        if(er) continue;
        vector<int> c;
        if(cnt == other) {
            int now = 0;
            for(int j = 0; j < 2 * (k + 1); j += 2) {
                vector<int> a;
                for(int z = now + has + ((i >> j) & 1) + ((i >> j + 1) & 1) - 1; z >= now; z -= 8) {
                    int tmp = 0;
                    int p = 1;
                    for(int k = 0; k < 8; k ++ ){
                        if(z - k >= now)tmp += (s[z - k] - '0') * p;
                        p *= 10;
                    }
                    a.push_back(tmp);
                    // cout << z << ' ' << tmp << '\n';
                }
                // print(a);
                now = now + has + ((i >> j) & 1) + ((i >> j + 1) & 1);
                c = add(c, a);
            }
            // print(c);
            // cout << '\n';
            if(ans.size() == 0) {
                ans = c;
            } else {
                if(cmp(ans, c)) {
                    ans = c;
                }
            }
        }
    }
    // 8174657
    // if(ans.size() == 25 && ans[0] == 8 && ans[1] == 1 && ans[2] == 7 && ans[3] == 4 && ans[4] == 6 && ans[5] == 5 && ans[6] == 7){
    //     cout << k << "?" << s.size() << "?" << s << '\n';
    // }
    print(ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int t = 1;
    cin >> t;
    while(t -- ) {
        solve();
    }

    return 0;
}

answer.code:22:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
answer.code:29:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
answer.code:31:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
answer.code:45:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
answer.code:55:58: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   55 | vector<int> add(const vector<int> &a,const vector<int> &b) {
      |                                                          ^
answer.code:55:58: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:55:58: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:55:58: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:69:32: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   69 | void print(const vector<int> &c) {
      |                                ^
answer.code:69:32: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:69:32: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:69:32: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:79:52: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   79 | bool cmp(const vector<int> &a, const vector<int> &b) {
      |                                                    ^
answer.code:79:52: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:79:52: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:79:52: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:12: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   90 | void solve() {
      |            ^
answer.code:90:12: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:12: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:12: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:213:10: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
  213 | int main() {
      |          ^
answer.code:213:10: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:213:10: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:213:10: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:49:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/basic_string.h:181:14: note: called from here
  181 |       struct _Alloc_hider : allocator_type // TODO check __is_final
      |              ^~~~~~~~~~~~