#include<bits/stdc++.h>
using namespace std;

const int N = 200010;

int A[N], B[N], C[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while(T -- ) {
        int n, k;
        string str;
        cin >> n >> k >> str;
        reverse(str.begin(), str.end());

        int rem = n % (k + 1), d = n / (k + 1);
        vector<int> states;
        for(int i = 0; i < (1 << (k + 1)); i ++ ) {
            int cnt = 0;
            for(int j = 0; j < k + 1; j ++ ) cnt += (i >> j & 1);
            if(cnt == rem) {
                states.push_back(i);
            }
        }

        auto getval = [&](int v[], int l, int r) -> void {
            for(int i = 0; i < r - l + 1; i ++ ) {
                v[i] = str[l + i] - '0';
            }
        };

        auto add = [&](int v1[], int v2[], int &len1, int len2) -> void {
            int t = 0;
            len1 = max(len1, len2);
            for(int i = 0; i < len2; i ++ ) {
                t += v1[i] + v2[i];
                v1[i] = t % 10;
                t /= 10;
            }
            for(int i = len2; i < len1; i ++ ) {
                t += v1[i];
                v1[i] = t % 10;
                t /= 10;
            }
            while(t) {
                v1[len1 ++ ] = t % 10;
                t /= 10;
            }
        };

        auto take = [&](int v1[], int v2[], int &len1, int &len2) -> void {
            bool high = true;
            if(len1 != len2 && len1 < len2) high = false;
            else if(len1 == len2) {
                for(int i = len1 - 1; i >= 0; i -- ) {
                    if(v1[i] != v2[i]) {
                        if(v1[i] < v2[i]) high = false;
                        break;
                    }
                }
            }
            if(!high) {
                len1 = len2;
                for(int i = len2 - 1; i >= 0; i -- ) v1[i] = v2[i];
            }
        };

        int m = 0;
        for(int i = 0; i < n + 5; i ++ ) C[i] = 0;
        for(auto state : states) {
            int len = 0, last = -1;
            for(int i = 0; i < n + 5; i ++ ) A[i] = B[i] = 0;
            for(int j = 0; j < k + 1; j ++ ) {
                int l = last + 1, r = (state >> j & 1 ? l + d : l + d - 1);
                getval(B, l, r);
                add(A, B, len, r - l + 1);
                last = r;
            }
            take(C, A, m, len);
        }
        for(int i = m - 1; i >= 0; i -- ) cout << C[i];
        cout << '\n';
    }
    return 0;
}