<image>

William really likes the cellular automaton called "Game of Life" so he decided to make his own version. For simplicity, William decided to define his cellular automaton on an array containing n cells, with each cell either being alive or dead.

Evolution of the array in William's cellular automaton occurs iteratively in the following way:

  * If the element is dead and it has exactly 1 alive neighbor in the current state of the array, then on the next iteration it will become alive. For an element at index i the neighbors would be elements with indices i - 1 and i + 1. If there is no element at that index, it is considered to be a dead neighbor. 
  * William is a humane person so all alive elements stay alive. 



Check the note section for examples of the evolution.

You are given some initial state of all elements and you need to help William find the state of the array after m iterations of evolution.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^3). Description of the test cases follows.

The first line of each test case contains two integers n and m (2 ≤ n ≤ 10^3, 1 ≤ m ≤ 10^9), which are the total number of cells in the array and the number of iterations.

The second line of each test case contains a string of length n made up of characters "0" and "1" and defines the initial state of the array. "1" means a cell is alive and "0" means it is dead.

It is guaranteed that the sum of n over all test cases does not exceed 10^4.

Output

In each test case output a string of length n, made up of characters "0" and "1" — the state of the array after m iterations of evolution.

Example

Input


4
11 3
01000000001
10 2
0110100101
5 2
10101
3 100
000


Output


11111001111
1110111101
10101
000

Note

Sequence of iterations of evolution for the first test case 

  * 01000000001 — initial state 
  * 11100000011 — first iteration of evolution 
  * 11110000111 — second iteration of evolution 
  * 11111001111 — third iteration of evolution 



Sequence of iterations of evolution for the second test case 

  * 0110100101 — initial state 
  * 1110111101 — first iteration of evolution 
  * 1110111101 — second iteration of evolution 
import java.util.*;
import java.io.*;

public class CF1 implements Runnable {

    static FastReader sc;
    static PrintWriter out;
    static int mod = 1000000007;

    public static void main(String[] args) {
        new Thread(null, new CF1(), "coderrohan14", 1 << 26).start();
    }

    @Override
    public void run() {
        try {
            ioSetup();
        } catch (IOException e) {
            return;
        }
    }

    public static void ioSetup() throws IOException {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            File f1 = new File("input.txt");
            File f2 = new File("output.txt");
            Reader r = new FileReader(f1);
            sc = new FastReader(r);
            out = new PrintWriter(f2);
            double prev = System.currentTimeMillis();
            solve();
            out.println("\n\nExecuted in : " + ((System.currentTimeMillis() - prev) / 1e3) + " sec");
        } else {
            sc = new FastReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            solve();
        }
        out.flush();
        out.close();
    }

    static void solve() {
        int t = sc.nextInt();
        StringBuilder ans = new StringBuilder("");
        while (t-- > 0) {
            int n = sc.nextInt(), m = sc.nextInt();
            char[] arr = sc.next().toCharArray();
            int cnt = 0;
            while (cnt < m) {
                boolean z = false;
                for (int i = 0; i < n; i++) {
                    if (arr[i] == '1') {
                        if (i + 1 < n && arr[i + 1] == '0') {
                            if (i + 2 < n && arr[i + 2] == '1') {

                            } else {
                                z = true;
                                arr[i + 1] = '3';
                            }
                        }
                        if (i - 1 >= 0 && arr[i - 1] == '0') {
                            if (i - 2 >= 0 && arr[i - 2] == '1') {

                            } else {
                                z = true;
                                arr[i - 1] = '3';
                            }
                        }
                    }
                }
                for (int i = 0; i < n; i++) {
                    if (arr[i] == '3') {
                        arr[i] = '1';
                    }
                }
                if (!z)
                    break;
                cnt++;
            }
            for (int i = 0; i < n; i++) {
                ans.append(arr[i]);
            }
            ans.append("\n");
        }
        out.println(ans);
    }

    /****************************************************************************************************************************************************************************************/

    static long modInverse(long a, int mod) {
        long g = gcd(a, mod);
        if (g != 1)
            return -1;
        else {
            return modPower(a, mod - 2L, mod);
        }
    }

    static long modPower(long x, long y, int mod) {
        long res = 1;
        x = x % mod;
        if (x == 0)
            return 0;
        while (y > 0) {
            if ((y & 1) != 0)
                res = (res * x) % mod;
            y = y >> 1;
            x = (x * x) % mod;
        }
        return res;
    }

    static int gcd(int a, int b) {
        int tmp = 0;
        while (b != 0) {
            tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    static long gcd(long a, long b) {
        long tmp = 0;
        while (b != 0) {
            tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    static boolean isPrime(long n) {
        if (n == 2 || n == 3)
            return true;
        if (n % 2 == 0)
            return false;
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0)
                return false;
        }
        return n != 1;
    }

    static boolean isPerfectSquare(long x) {
        long sqrt = (long) Math.sqrt(x);
        return (sqrt * sqrt) == x;
    }

    static int digitsCount(long x) {
        return (int) Math.floor(Math.log10(x)) + 1;
    }

    static boolean isPowerTwo(long n) {
        return (n & n - 1) == 0;
    }

    static void sieve(boolean[] prime, int n) { // Sieve Of Eratosthenes
        for (int i = 1; i <= n; i++) {
            prime[i] = true;
        }
        for (int i = 2; i * i <= n; i++) {
            if (prime[i]) {
                for (int j = 2; i * j <= n; j++) {
                    prime[i * j] = false;
                }
            }
        }
    }

    static long nCr(long n, long r) { // Combinations
        if (n < r)
            return 0;
        if (r > n - r) { // because nCr(n, r) == nCr(n, n - r)
            r = n - r;
        }
        long ans = 1L;
        for (long i = 0; i < r; i++) {
            ans *= (n - i);
            ans /= (i + 1);
        }
        return ans;
    }

    static int floor(int[] a, int v) {
        int l = 0, h = a.length - 1;
        while (l < h) {
            int mid = (l + h) / 2;
            if (a[mid] == v)
                return mid;
            if (v < a[mid])
                h = mid;
            else {
                if (mid + 1 < h && a[mid + 1] < v)
                    l = mid + 1;
                else
                    return mid;
            }
        }
        return a[l] <= v ? l : -1;
    }

    static int floor(long[] a, long v) {
        int l = 0, h = a.length - 1;
        while (l < h) {
            int mid = (l + h) / 2;
            if (a[mid] == v)
                return mid;
            if (v < a[mid])
                h = mid;
            else {
                if (mid + 1 < h && a[mid + 1] < v)
                    l = mid + 1;
                else
                    return mid;
            }
        }
        return a[l] <= v ? l : -1;
    }

    static int ceil(int[] a, int v) {
        int l = 0, h = a.length - 1;
        while (l < h) {
            int mid = (l + h) / 2;
            if (a[mid] == v)
                return mid;
            if (a[mid] < v)
                l = mid + 1;
            else
                h = mid;
        }
        return a[h] >= v ? h : -1;
    }

    static int ceil(long[] a, long v) {
        int l = 0, h = a.length - 1;
        while (l < h) {
            int mid = (l + h) / 2;
            if (a[mid] == v)
                return mid;
            if (a[mid] < v)
                l = mid + 1;
            else
                h = mid;
        }
        return a[h] >= v ? h : -1;
    }

    static long catalan(int n) { // n-th Catalan Number
        long c = nCr(2 * n, n);
        return c / (n + 1);
    }

    static class Pair implements Comparable<Pair> { // Pair Class
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Pair)) {
                return false;
            }

            Pair pair = (Pair) o;

            if (x != pair.x) {
                return false;
            }
            if (y != pair.y) {
                return false;
            }

            return true;
        }

        @Override
        public int hashCode() {
            long result = x;
            result = 31 * result + y;
            return (int) result;
        }

        @Override
        public int compareTo(Pair o) {
            return (int) (this.x - o.x);
        }
    }

    static class Trip { // Triplet Class
        long x;
        long y;
        long z;

        Trip(long x, long y, long z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Trip)) {
                return false;
            }

            Trip trip = (Trip) o;

            if (x != trip.x) {
                return false;
            }
            if (y != trip.y) {
                return false;
            }
            if (z != trip.z) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            long result = 62 * x + 31 * y + z;
            return (int) result;
        }
    }

    /**************************************************************************************************************************************************************************************/

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(Reader r) {
            br = new BufferedReader(r);
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] readArrayI(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            return arr;
        }

        long[] readArrayL(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextLong();
            }
            return arr;
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    /*
     * ASCII Range--->(A-Z)--->[65,90]<<::>>(a-z)--->[97,122]
     */
    /******************************************************************************************************************/

    static void printArray(int[] arr) {
        out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i < arr.length - 1)
                out.print(arr[i] + ",");
            else
                out.print(arr[i]);
        }
        out.print("]");
        out.println();
    }

    static void printArray(long[] arr) {
        out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i < arr.length - 1)
                out.print(arr[i] + ",");
            else
                out.print(arr[i]);
        }
        out.print("]");
        out.println();
    }

    static void printArray(double[] arr) {
        out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i < arr.length - 1)
                out.print(arr[i] + ",");
            else
                out.print(arr[i]);
        }
        out.print("]");
        out.println();
    }
    /**********************************************************************************************************************/
}