#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define deb(...)
#endif
using namespace std;
#define ll long long
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define db double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
#define bug(x) (void)(cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl)
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
using uint = unsigned;
const int MOD = 998244353;  // NTT模数
struct bigint {
    vector<int> nums;  // 存储大整数的每一位
    int operator[](const int& k) const { return nums[k]; }
    int& operator[](const int& k) { return nums[k]; }
    int size() { return nums.size(); }
    void push_back(int x) { nums.push_back(x); }
    // 从整数构造大整数
    bigint(int x = 0) {
        do {
            nums.push_back(x % 10);
            x /= 10;
        } while (x);
    }
    // 从字符串构造大整数
    bigint(string s) {
        for (int i = s.size() - 1; i >= 0; i--)
            nums.push_back(s[i] - '0');
        trim();
    }
    // 去掉多余的前导零
    void trim() {
        while (nums.size() > 1 && nums.back() == 0) {
            nums.pop_back();
        }
    }
    // 清空大整数
    void clear() {
        nums.clear();
    }
    // 输入大整数
    friend istream& operator>>(istream& cin, bigint& num) {
        string tnum;
        cin >> tnum;
        num = tnum;
        return cin;
    }
    // 输出大整数
    friend ostream& operator<<(ostream& cout, bigint num) {
        bool start = false;
        for (int i = num.size() - 1; i >= 0; i--) {
            if (!start && num[i] == 0)
                continue;
            start = true;
            cout << num[i];
        }
        if (!start)
            cout << 0;
        return cout;
    }
};

// 比较运算符重载
bool operator<(bigint a, bigint b) {
    if (a.size() != b.size())
        return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; i--)
        if (a[i] != b[i])
            return a[i] < b[i];
    return false;
}

bool operator>(bigint a, bigint b) {
    return b < a;
}

bool operator<=(bigint a, bigint b) {
    return !(a > b);
}

bool operator>=(bigint a, bigint b) {
    return !(a < b);
}

bool operator==(bigint a, bigint b) {
    return !(a < b) && !(a > b);
}

bool operator!=(bigint a, bigint b) {
    return a < b || a > b;
}

// 大整数加法
bigint operator+(bigint a, bigint b) {
    bigint res;
    res.clear();
    int t = 0;
    int mx = max(a.size(), b.size());
    for (int i = 0; i < mx || t; i++) {
        if (i < a.size()) {
            t += a[i];
        }
        if (i < b.size()) {
            t += b[i];
        }
        res.push_back(t % 10);
        t /= 10;
    }
    res.trim();
    return res;
}

// 大整数减法
bigint operator-(bigint a, bigint b) {
    bigint res(a);
    bigint sub(b);
    int flag = 0;
    int len = res.size();
    while (sub.size() < res.size())
        sub.push_back(0);
    for (int i = 0; i < len; i++) {
        if (res[i] + flag >= sub[i]) {
            res[i] = res[i] + flag - sub[i];
            flag = 0;
        } else {
            res[i] = res[i] + 10 + flag - sub[i];
            flag = -1;
        }
    }
    res.trim();
    return res;
}
int n, k;
void solve2() {
    int avg = n / (k + 1);
    // int lef = n % (k + 1);
    string s;
    cin >> s;
    s = " " + s;
    // string infmx;
    // for (int i = 0; i < n; i++) infmx += '9';
    // // cout << infmx << endl;
    ll ans = 1e18 - 1;
    auto cal = [&](vector<int>& len, ll& res) {
        int cur = 1;
        assert((int)len.size() == (k + 1));
        for (int i = 0; i < k + 1; i++) {
            res = res + stoll(s.substr(cur, len[i]));
            cur += len[i];
        }
        assert(cur == n + 1);
    };
    vector<int> len;
    auto dfs = [&](auto self, int u, int cur, int last, int mx, int mn) {
        if (mx - mn >= 3)
            return;
        if (u == k + 1) {
            ll res(0);
            if (cur != n + 1)
                return;
            cal(len, res);
            if (res < ans)
                ans = res;
            return;
        }
        if (u == 0) {
            for (int i = max(avg - 2, 1); i <= min(avg + 2, n); i++) {
                len.push_back(i);
                self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
                len.pop_back();
            }
        } else {
            for (int i = max(last - 1, 1); i <= min(last + 1, n); i++) {
                len.push_back(i);
                self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
                len.pop_back();
            }
        }
    };
    dfs(dfs, 0, 1, 0, 0, inf);
    cout << ans << endl;
}
void solve() {
    cin >> n >> k;

    if (n <= 18) {
        solve2();
        return;
    }
    deb(n, k);
    int avg = n / (k + 1);
    // int lef = n % (k + 1);
    string s;
    cin >> s;
    s = " " + s;
    string infmx;
    for (int i = 0; i < n; i++) infmx += '9';
    // cout << infmx << endl;
    bigint ans(infmx);
    auto cal = [&](vector<int>& len, bigint& res) {
        int cur = 1;
        assert((int)len.size() == (k + 1));
        for (int i = 0; i < k + 1; i++) {
            res = res + bigint(s.substr(cur, len[i]));
            cur += len[i];
        }
        assert(cur == n + 1);
    };
    vector<int> len;
    auto dfs = [&](auto self, int u, int cur, int last, int mx, int mn) {
        if (mx - mn >= 3)
            return;
        if (cur > n + 1)
            return;
        if (cur + k + 1 - u > n + 1)
            return;
        if (cur + (mn + 2) * (k + 1 - u) < n + 1)
            return;

        if (u == k + 1) {
            bigint res(0);
            if (cur != n + 1)
                return;
            cal(len, res);
            if (res < ans)
                ans = res;
            return;
        }
        if (u == 0) {
            for (int i = max(avg - 2, 1); i <= min(avg + 2, n); i++) {
                len.push_back(i);
                self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
                len.pop_back();
            }
        } else {
            for (int i = max(last - 1, 1); i <= min(last + 1, n); i++) {
                len.push_back(i);
                self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
                len.pop_back();
            }
        }
    };
    dfs(dfs, 0, 1, 0, 0, inf);
    cout << ans << endl;
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef LOCAL
    double starttime = clock();
    // freopen("in.txt", "r", stdin);
    //  freopen("out.txt", "w", stdout);
#endif
    int t = 1;
    cin >> t;
    while (t--) solve();
#ifdef LOCAL
    double endtime = clock();
    cerr << "Time Used: " << (double)(endtime - starttime) / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
    return 0;
}

answer.code: In function ‘void solve2()’:
answer.code:169:20: error: use of ‘auto’ in lambda parameter declaration only available with ‘-std=c++14’ or ‘-std=gnu++14’
  169 |     auto dfs = [&](auto self, int u, int cur, int last, int mx, int mn) {
      |                    ^~~~
answer.code: In lambda function:
answer.code:184:21: error: ‘self’ cannot be used as a function
  184 |                 self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:190:21: error: ‘self’ cannot be used as a function
  190 |                 self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘void solve2()’:
answer.code:195:8: error: no match for call to ‘(solve2()::<lambda(int, int, int, int, int, int)>) (solve2()::<lambda(int, int, int, int, int, int)>&, int, int, int, int, const int&)’
  195 |     dfs(dfs, 0, 1, 0, 0, inf);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~
answer.code:169:16: note: candidate: ‘solve2()::<lambda(int, int, int, int, int, int)>’
  169 |     auto dfs = [&](auto self, int u, int cur, int last, int mx, int mn) {
      |                ^
answer.code:169:16: note:   no known conversion for argument 1 from ‘solve2()::<lambda(int, int, int, int, int, int)>’ to ‘int’
answer.code: In function ‘void solve()’:
answer.code:225:20: error: use of ‘auto’ in lambda parameter declaration only available with ‘-std=c++14’ or ‘-std=gnu++14’
  225 |     auto dfs = [&](auto self, int u, int cur, int last, int mx, int mn) {
      |                    ^~~~
answer.code: In lambda function:
answer.code:247:21: error: ‘self’ cannot be used as a function
  247 |                 self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:253:21: error: ‘self’ cannot be used as a function
  253 |                 self(self, u + 1, cur + i, i, max(mx, i), min(i, mn));
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘void solve()’:
answer.code:258:8: error: no match for call to ‘(solve()::<lambda(int, int, int, int, int, int)>) (solve()::<lambda(int, int, int, int, int, int)>&, int, int, int, int, const int&)’
  258 |     dfs(dfs, 0, 1, 0, 0, inf);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~
answer.code:225:16: note: candidate: ‘solve()::<lambda(int, int, int, int, int, int)>’
  225 |     auto dfs = [&](auto self, int u, int cur, int last, int mx, int mn) {
      |                ^
answer.code:225:16: note:   no known conversion for argument 1 from ‘solve()::<lambda(int, int, int, int, int, int)>’ to ‘int’