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

#define FOR(i, from, to) for (int i = (from); i <= int(to); ++i)
#define FORN(i, n) FOR(i, 0, (n) - 1)
#define endl '\n'
#define F first
#define S second

template<typename T>
bool rMin(T& v, const T& rval)
{
    if (rval < v) {
        v = rval;
        return true;
    }
    return false;
}

template<typename T>
bool rMax(T& v, const T& rval)
{
    if (v < rval) {
        v = rval;
        return true;
    }
    return false;
}

const int N = 2e5;
const int INF = 2 * (N + 1);
struct Dp {
    int val;
    int min_open, max_open;
} dp[N][2];

bool a[N];
int n;

Dp merge(Dp a, Dp b)
{
    auto val = min(a.val, b.val);
    int min_open = N + 1, max_open = 0;
    auto relax = [&](Dp d){
        if (val == d.val) {
            rMin(min_open, d.min_open);
            rMax(max_open, d.max_open);
        }
    };
    relax(a);
    relax(b);
    return {val, min_open, max_open};
}

pair<Dp, Dp> states(int i, int v, const int C)
{
    Dp open_new = dp[i - 1][!v];
    open_new.val += C, ++open_new.min_open, ++open_new.max_open;
    Dp cont_old = dp[i - 1][v];
    return {open_new, cont_old};
}

Dp calc(const int C, const int st, const int fn)
{
    dp[0][st] = {C, 1, 1};
    dp[0][!st] = {INF, -1, -1};
    dp[0][!a[0]].val += 2;
    FOR(i, 1, n - 1)
        FORN(v, 2) {
            Dp open_new, cont_old;
            tie(open_new, cont_old) = states(i, v, C);
            dp[i][v] = merge(open_new, cont_old);
            if (a[i] != v)
                dp[i][v].val += 2;
        }
    return dp[n - 1][fn];
}

bool ans[N];

void mod(int& k, int st, int fn)
{
    if (st == fn && k % 2 == 0)
        --k;
    if (st != fn && k % 2 == 1)
        --k;
}

bool restore(const int C, int k, const int s, const int f)
{
    mod(k, s, f);
    auto fn = calc(C, s, f);
    auto val = fn.val;
    if (k > fn.max_open) {
        assert(C == 0);
        k = fn.max_open;
    }
    auto check = [&val, &k](Dp d){
        return d.val == val && d.min_open <= k && k <= d.max_open;
    };
    int i = n - 1, v = f;
    for (; i != 0; --i) {
        ans[i] = v;
        val = dp[i][v].val;
        if (a[i] != v)
            val -= 2;
        Dp open_new, cont_old;
        tie(open_new, cont_old) = states(i, v, C);
        if (check(cont_old)) {
            continue;
        }
        if (check(open_new)) {
            --k;
            v = !v;
            continue;
        }
        assert(false);
    }
    ans[0] = v;
    return true;
}


pair<int, int> res(int st, int fn, int k)
{
    mod(k, st, fn);
    if (k == 0)
        return {INF, -1};
    int l = -1, r = INF;
    while (l + 1 != r) {
        auto m = (l + r) / 2;
        if (calc(m, st, fn).min_open > k)
            l = m;
        else
            r = m;
    }
    return {calc(r, st, fn).val - k * r, r};
}

void solve()
{
    int k;
    cin >> n >> k;
    FORN(i, n) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }

    pair<int, int> best = {INF, -1};
    int bSt = -1, bFn = -1;
    FORN(st, 2) {
        FORN(fn, 2) {
            if (rMin(best, res(st, fn, k)))
                bSt = st, bFn = fn;
        }
    }

    restore(best.S, k, bSt, bFn);
    FORN(i, n)
        cout << ans[i];
    cout << endl;
}


int main()
{
#ifdef MY
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    #define FILEIO(TASK) do { freopen(TASK".in", "r", stdin); freopen(TASK".out", "w", stdout); } while (false)
    FILEIO("penguins");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#endif // MY
    int t;
    cin >> t;
    FOR(i, 1, t) {
        solve();
    }
}