//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
                // http://xorshift.di.unimi.it/splitmix64.c
                x += 0x9e3779b97f4a7c15;
                x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
                static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
                return splitmix64(x + FIXED_RANDOM);
        }
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T rand(T a, T b){
    return uniform_int_distribution<T>(a, b)(rng);
}

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;


#define rep(i, a, b) for(int i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
//#define int long long

const ll mod = 998244353;
const ll INF = 1e18;

/* ----------------------------------------------------- GO DOWN ---------------------------------------------------------------------- */

bool comp (int dig1[], int dig2[], int len) {
        for (int i = len - 1; i >= 0; i--) {
                if (dig1[i] < dig2[i]) return false;
                if (dig1[i] > dig2[i]) return true;
        }
        return false;
}


signed main() {

        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int t;
        cin >> t;

        while (t--) {

                int n, k;
                cin >> n >> k;
                k++;
                string s;
                cin >> s;
                int len = 2 * (n + k - 1) / k + 10;
                int dig1[len];
                for (int i = 0; i < len; i++) dig1[i] = 9;
                int y = n / k;
                int z = n % k;
                if (z > k / 2) {
                        y++;
                        z -= k;
                }

                int tot = 1;
                for (int i = 0; i < k; i++) tot *= 3;

                for (int mask = 0; mask < tot; mask++) {
                        
                        int del = 0;
                        int mk = mask;
                        bool neg1 = 0;
                        for (int j = 0; j < k; j++) {
                                del += (mk % 3) - 1;
                                if (mk % 3 == 0) neg1 = 1; 
                                mk /= 3;
                        }
                        if (neg1 && y <= 1) continue;
                        if (del != z) continue;

                        mk = mask;
                        int l = 0;
                        int dig2[len] = {0};
                        for (int it = 0; it < k; it++) {
                                int r = l + y + (mk % 3 - 1);                                
                                int car = 0;
                                int i = 0;
                                for (int j = r - 1; j >= l; j--, i++) {
                                        dig2[i] += (int)s[j] - '0' + car;
                                        car = 0;
                                        if (dig2[i] > 9) {
                                                dig2[i] -= 10;
                                                car = 1;
                                        }
                                }
                                l = r;
                                while (car) {
                                        dig2[i] += car;
                                        car = 0;
                                        if (dig2[i] > 9) {
                                                dig2[i] -= 10;
                                                car = 1;
                                        }
                                        i++;
                                }
                                mk /= 3;
                        }

                        if (comp(dig1, dig2, len)) {
                                for (int i = 0; i < len; i++) dig1[i] = dig2[i]; 
                        }

                }

                int r = len - 1;
                while (dig1[r] == 0) r--;
                while (r >= 0) {
                        cout << dig1[r];
                        r--;
                }
                cout << "\n";


        }
        
       
}