#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
const int N = 3e5+5, M = 2e6;
int n, k, base;
char s[N];
char res[N];
char ans[N];
int lenans;

void update_ans(vector<int> len) {
  sort(begin(len), end(len));
  int ul = *len.rbegin();
      do {
        vector<int> p(k);
        for (int i = 1; i < k; ++i) p[i] += len[i-1];
        char carry = 0;
        int lenres = 0;
        for (int i = 0; i < ul; ++i) {
          char cur = carry;
          for (int j = 0; j < k; ++j) if (i < len[j]) {
            cur += s[p[j]+i];
          }
          res[i] = cur % 10;
          carry = cur / 10;
          ++lenres;
        }
        if (carry) res[lenres++] = carry;
        bool upd = 0;
        if (lenres < lenans) upd = 1;
        else if (lenres == lenans) {
          for (int i = lenres - 1; i >= 0; --i) {
            if (res[i] < ans[i]) {
              upd = 1;
              break;
            }
          }
        }
        if (upd) {
          for (int i = 0; i < lenres; ++i) ans[i] = res[i];
          lenans = lenres;
        }

      } while (next_permutation(begin(len), end(len)));
}

int val[10];

void dfs(int i, int len, int s) {
  if (i == 7) {
    if (len == k && s == n) {
    vector<int> p;
    for (int j = 0; j < k; ++j) p.push_back(val[j]);
    update_ans(p);
    }
    return;
  }
  if (base+i-3<1) return dfs(i+1,len,s);
  if (len > k || s > n) return;
  for (int j = 0; j <= k; ++j) {
    for (int l = 0; l < j; ++l) val[len+l] = base+i-3;
    dfs(i+1,len+j, s+j*(base+i-3));
  }
}

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
      cin >> n >> k >> s;
      k = min(k+1, n);
      for (int i = 0; i < n; ++i) s[i] -= '0';
      memcpy(ans, s, n);
      lenans = n;
      reverse(s, s+n);
      base = n/k;
      // vector<int> len(k, n/k);
      // for (int i = 0; i < n%k; ++i) len[k-i-1]+=1;
      // update_ans(len);
      dfs(0,0,0);
      for (int i = lenans-1; i >= 0; --i) {
        cout << char(ans[i]+'0');
      }
      cout << '\n';
    }
    return 0;
}