<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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class CodeForces {

    public static void main(String[] args) throws IOException {
        reader input = new reader();
        PrintWriter output = new PrintWriter(System.out);
        //BufferedReader bf = new BufferedReader(new FileReader("input.txt"));
        //PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
        //StringTokenizer stk = new StringTokenizer(bf.readLine());
        //int n=Integer.parseInt(stk.nextToken());
        int t=input.nextInt();
        for(int i=0;i<t;i++){
            int n=input.nextInt();
            int m=input.nextInt();
            char arr[]=input.next().toCharArray();
            LinkedList<Integer>q=new LinkedList<>();
            if(n>=2){
                if(arr[1]=='1'&&arr[0]=='0')
                    q.add(0);
            }
            for(int j=1;j<=n-2;j++){
                if((arr[j]=='0'&&arr[j-1]=='1'&&arr[j+1]=='0')||(arr[j]=='0'&&arr[j-1]=='0'&&arr[j+1]=='1')){
                    q.add(j);
                }
            }
            if(n>=2){
                if(arr[n-1]=='0'&&arr[n-2]=='1')
                    q.add(n-1);
            }
            int count=0;
            while(!q.isEmpty()&&count<m){
                int temp=q.size();
                for(int j=0;j<temp;j++){
                    int x=q.poll();
                    arr[x]='1';
                    if(x-2>=0&&arr[x-1]=='0'&&arr[x-2]=='0')
                        q.add(x-1);
                    if(x+2<n&&arr[x+1]=='0'&&arr[x+2]=='0'&&(q.isEmpty()||q.peek()!=x+2))
                        q.add(x+1);
                    if(x==1&&arr[0]=='0')
                        q.add(0);
                    if(x==n-2&&arr[n-1]=='0')
                        q.add(n-1);
                }
                count++;
            }
            for(int j=0;j<n;j++)
                output.print(arr[j]);
            output.println();
        }
        output.close();
    }

    public static boolean isPrime(long num){
        if(num==1)
            return false;
        else if(num==2||num==3)
            return true;
        else if(num%2==0||num%3==0)
            return false;
        else{
            for(long i=5;i*i<=num;i+=6){
                if(num%i==0||num%(i+2)==0)
                    return false;
            }
        }
        return true;
    }

    public static void mergesort(long arr[],int start,int end){//start and end must be indexes
        if(start<end) {
            int mid=(start+end)/2;
            mergesort(arr,start,mid);
            mergesort(arr, mid+1, end);
            merge(arr, start,mid,end);
        }
    }
    public static void merge(long arr[],int start,int mid,int end){
        int lsize=mid-start+1,rsize=end-mid;
        long l[]=new long[lsize],r[]=new long[rsize];
        for(int i=start;i<=mid;i++){
            l[i-start]=arr[i];
        }
        for(int i=mid+1;i<=end;i++){
            r[i-mid-1]=arr[i];
        }
        int i=0,j=0,k=start;
        while(i<lsize&&j<rsize){
            if(l[i]<=r[j]){
                arr[k++]=l[i++];
            }else{
                arr[k++]=r[j++];
            }
        }
        while(i<lsize)
            arr[k++]=l[i++];
        while(j<rsize)
            arr[k++]=r[j++];
    }
}
class Node{
    long curr;
    int index;
    Node(long curr,int index){
        this.curr=curr;
        this.index=index;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Node)) return false;
        Node node = (Node) o;
        return curr == node.curr &&
                index == node.index;
    }

    @Override
    public int hashCode() {
        return Objects.hash(curr, index);
    }
}
class Tree{
    int n;
    int v;
    Tree(int n,int v){
        this.n=n;
        this.v=v;
    }
}

class Edge{
    int src,dest,weight;
    Edge(int src,int dest,int weight){
        this.src=src;
        this.dest=dest;
        this.weight=weight;
    }
}

class TempEdge{
    int vertex;
    long distance;
    TempEdge(int vertex,long distance){
        this.vertex=vertex;
        this.distance=distance;
    }
}

//Undirected Graph
class UGraph{
    ArrayList<ArrayList<Edge>>graph;
    int vertex;
    UGraph(int vertex){
        this.vertex=vertex;
        graph=new ArrayList<>();
        for(int i=0;i<vertex;i++){
            graph.add(new ArrayList<>());
        }
    }
    void addEdge(int u,int v){
        graph.get(u).add(new Edge(u,v,0));
        graph.get(v).add(new Edge(v,u,0));
    }
    void addEdge(int u,int v,int weight){
        graph.get(u).add(new Edge(u,v,weight));
        graph.get(v).add(new Edge(v,u,weight));
    }
    ArrayList<Integer> BFS(int source){
        boolean visited[]=new boolean[vertex];
        ArrayList<Integer>ans=new ArrayList<>();
        LinkedList<Integer>q=new LinkedList<>();
        q.add(source);
        visited[source]=true;
        while(!q.isEmpty()){
            int x=q.removeFirst();
            ans.add(x);
            for(Edge i:graph.get(x)){
                if(!visited[i.dest]){
                    q.add(i.dest);
                    visited[i.dest]=true;
                }
            }
        }
        return ans;
    }
    ArrayList<Integer> BFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        ArrayList<Integer>ans=new ArrayList<>();
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                ArrayList<Integer>temp=BFS(i);
                for(int j:temp)
                    ans.add(j);
            }
        }
        return ans;
    }
    int connectedComponentsBFS(){
        boolean visited[]=new boolean[vertex];
        int count=0;
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                count++;
                BFS(i);
            }
        }
        return count;
    }
    void DFS(int source){
        boolean visited[]=new boolean[vertex];
        DFSHelper(source,visited);
        System.out.println();
    }
    void DFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                DFSHelper(i,visited);
                System.out.println();
            }
        }
    }
    void DFSHelper(int source,boolean visited[]){
        visited[source]=true;
        System.out.print(source+" ");
        for(Edge i:graph.get(source)){
            if(!visited[i.dest]){
                DFSHelper(i.dest,visited);
            }
        }
    }
    boolean detectCycleDFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        for (int i=0;i<vertex;i++){
            if(!visited[i]){
                if(detectCycleDFSHelper(i,-1,visited))
                    return true;
            }
        }
        return false;
    }
    boolean detectCycleDFSHelper(int source,int parent,boolean visited[]){
        visited[source]=true;
        for(Edge i:graph.get(source)){
            if(!visited[i.dest]){
                if(detectCycleDFSHelper(i.dest,source,visited))
                    return true;
            }
            if(i.dest!=parent)
                return true;
        }
        return false;
    }
    boolean detectCycleBFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        for (int i=0;i<vertex;i++){
            if(!visited[i]){
                if(detectCycleBFSHelper(i,visited))
                    return true;
            }
        }
        return false;
    }
    boolean detectCycleBFSHelper(int source,boolean visited[]){
        int parent[]=new int[vertex];
        Arrays.fill(parent,-1);
        LinkedList<Integer>q=new LinkedList<>();
        q.add(source);
        visited[source]=true;
        while(!q.isEmpty()){
            int x=q.removeFirst();
            for(Edge i:graph.get(x)){
                if(!visited[i.dest]){
                    q.add(i.dest);
                    visited[i.dest]=true;
                    parent[i.dest]=x;
                }
                else{
                    if(parent[x]!=i.dest)
                        return true;
                }
            }
        }
        return false;
    }
    int primsMST(){
        boolean MST[]=new boolean[vertex];
        TempEdge distarr[]=new TempEdge[vertex];//MST edge stores least distance of a vertex to the MST
        for(int i=0;i<vertex;i++) {
            distarr[i] = new TempEdge(i, Integer.MAX_VALUE);
        }
        distarr[0].distance=0;
        // Use TreeSet instead of PriorityQueue as the remove function of the PQ is O(n) in java
        //TreeSet adding elements not working...figure it out
        TreeSet<TempEdge>q=new TreeSet<>((a,b)->(int)(a.distance-b.distance));
        for(int i=0;i<vertex;i++) {
            q.add(distarr[i]);
        }
        int ans=0;
        while(!q.isEmpty()){
            TempEdge x=q.pollFirst();
            ans+=x.distance;
            MST[x.vertex]=true;//Adding in MST
            for(Edge i:graph.get(x.vertex)){
                if(!MST[i.dest]){//Vertex not present in MST
                    if(distarr[i.dest].distance>i.weight){//Updating smallest distance from MST vertices to i.dest
                        q.remove(distarr[i.dest]);
                        distarr[i.dest].distance=i.weight;
                        q.add(distarr[i.dest]);
                    }
                }
            }
        }
        return ans;
    }
    long [] dikstra(int source){
        long ans[]=new long[vertex];
        boolean visited[]=new boolean[vertex];
        Arrays.fill(ans,Integer.MAX_VALUE);
        ans[source]=0;
        //TreeSet may be used as done in prims if removal is required
        PriorityQueue<TempEdge>pq=new PriorityQueue<>((a,b)-> (int) (a.distance-b.distance));
        int count=0;
        pq.add(new TempEdge(source,ans[source]));
        while(count!=vertex-1){//On doing vertex-1 times, last vertex is automatically finalised
            TempEdge x= pq.poll();
            if(!visited[x.vertex]){
                visited[x.vertex]=true;
                count++;
                for(Edge i:graph.get(x.vertex)){
                    /*Checking visited is not necessary as the won't affect the distance in any case
                    but will affect the heap*/
                    if(!visited[i.dest] && ans[i.dest]>ans[x.vertex]+i.weight){
                        ans[i.dest]=ans[x.vertex]+i.weight;
                        pq.add(new TempEdge(i.dest,ans[i.dest]));
                    }
                }
            }
        }
        return ans;
    }
    long[] bellmanford(int source){
        long ans[]=new long[vertex];
        ans[source]=0;
        for(int i=0;i<vertex-1;i++){//Considering paths of length 1 to paths of length (v-1) from source
            for(int j=0;j<vertex;j++){
                for(Edge k:graph.get(j)){
                    if(ans[k.dest]>ans[k.src]+ans[k.weight])
                        ans[k.dest]=ans[k.src]+ans[k.weight];
                }
            }
        }
        return ans;
    }
}

//Directed non-weighted Graph
class DGraph{
    ArrayList<ArrayList<Edge>>graph;
    int vertex;
    DGraph(int vertex){
        this.vertex=vertex;
        graph=new ArrayList<>();
        for(int i=0;i<vertex;i++){
            graph.add(new ArrayList<>());
        }
    }
    void addEdge(int src,int dest){
        graph.get(src).add(new Edge(src,dest,0));
    }
    void addEdge(int src,int dest,int weight){
        graph.get(src).add(new Edge(src,dest,weight));
    }

    boolean detectCycleDFS(){
        boolean visited[]=new boolean[vertex];
        boolean recst[]=new boolean[vertex];
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                if(detectCycleDFSHelper(i,visited,recst))
                    return true;
            }
        }
        return false;
    }
    boolean detectCycleDFSHelper(int index,boolean visited[],boolean recst[]){
        visited[index]=true;
        recst[index]=true;
        for(Edge i:graph.get(index)){
            if(!visited[i.dest]){
                if(detectCycleDFSHelper(i.dest,visited,recst))
                    return true;
            }else{
                if(recst[i.dest])//Back edge present
                    return true;
            }
        }
        recst[index]=false;
        return false;
    }
    ArrayList<Integer> topologicalSortingBFS(){//Kahn's Algorithm which is valid only for directed acyclic graphs
        ArrayList<Integer>ans=new ArrayList<>();
        int indegree[]=new int[vertex];
        for(int i=0;i<vertex;i++){
            for(Edge j:graph.get(i)){
                indegree[j.dest]++;
            }
        }
        LinkedList<Integer>q=new LinkedList<>();
        for(int i=0;i<vertex;i++){
            if(indegree[i]==0)
                q.add(i);
        }
        while(!q.isEmpty()){
            int i=q.removeFirst();
            ans.add(i);
            for(Edge x:graph.get(i)){
                if(--indegree[x.dest]==0){
                    q.add(x.dest);
                }
            }
        }
        return ans;
    }
    boolean detectCycleTopologicalSort(){
        int count=0;
        int indegree[]=new int[vertex];
        for(int i=0;i<vertex;i++){
            for(Edge j:graph.get(i)){
                indegree[j.dest]++;
            }
        }
        LinkedList<Integer>q=new LinkedList<>();
        for(int i=0;i<vertex;i++){
            if(indegree[i]==0)
                q.add(i);
        }
        while(!q.isEmpty()){
            int i=q.removeFirst();
            count++;
            for(Edge x:graph.get(i)){
                if(--indegree[x.dest]==0){
                    q.add(x.dest);
                }
            }
        }
        return (count!=vertex);
    }
    ArrayList<Integer> topologicalSortingDFS(){
        boolean visited[]=new boolean[vertex];
        ArrayDeque<Integer>recst=new ArrayDeque<>();
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                topologicalSortingDFSHelper(i,visited,recst);
            }
        }
        ArrayList<Integer>ans=new ArrayList<>();
        while(!recst.isEmpty())
            ans.add(recst.pop());
        return ans;
    }
    void topologicalSortingDFSHelper(int index,boolean visited[],ArrayDeque<Integer>recst){
        visited[index]=true;
        for(Edge i:graph.get(index)){
            if(!visited[i.dest])
                topologicalSortingDFSHelper(i.dest,visited,recst);
        }
        recst.push(index);
    }
    ArrayList<ArrayList<Integer>> stronglyConnectedComponentsKosaraju(){
        ArrayList<Integer>sortedbyendtime=topologicalSortingDFS();
        ArrayList<ArrayList<Edge>>transposegraph=new ArrayList<>();
        for(int i=0;i<vertex;i++){
            transposegraph.add(new ArrayList<>());
        }
        for(int i=0;i<vertex;i++){
            for(Edge j:graph.get(i)){
                transposegraph.get(j.dest).add(new Edge(j.dest,j.src, j.weight));
            }
        }
        ArrayList<ArrayList<Integer>>ans=new ArrayList<>();
        boolean visited[]=new boolean[vertex];
        for(int i:sortedbyendtime){
            if(!visited[i]){
                ArrayList<Integer>curr=DFSTopologicalSort(i,transposegraph,visited);
                ans.add(curr);
            }
        }
        return ans;
    }
    ArrayList<Integer> DFSTopologicalSort(int source,ArrayList<ArrayList<Edge>>graph,boolean visited[]){
        ArrayList<Integer> ans=new ArrayList<>();
        DFSTopologicalSortHelper(source,graph,visited,ans);
        return ans;
    }
    void DFSTopologicalSortHelper(int source,ArrayList<ArrayList<Edge>>graph,boolean visited[],ArrayList<Integer> ans) {
        visited[source]=true;
        ans.add(source);
        for(Edge i:graph.get(source)){
            if(!visited[i.dest])
                DFSTopologicalSortHelper(i.dest,graph,visited,ans);
        }
    }
    long[] bellmanford(int source){
        long ans[]=new long[vertex];
        ans[source]=0;
        for(int i=0;i<vertex-1;i++){//Considering paths of length 1 to paths of length (v-1) from source
            for(int j=0;j<vertex;j++){
                for(Edge k:graph.get(j)){
                    if(ans[k.dest]>ans[k.src]+ans[k.weight])
                        ans[k.dest]=ans[k.src]+ans[k.weight];
                }
            }
        }
        return ans;
    }
}

class reader {
    BufferedReader br;
    StringTokenizer st;

    public reader() {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }

    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());
    }

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

    public int[] nextIntArray(int arraySize) {
        int array[] = new int[arraySize];
        for (int i = 0; i < arraySize; i++) {
            array[i] = nextInt();
        }
        return array;
    }

    public long[] nextLongArray(int arraySize) {
        long array[] = new long[arraySize];
        for (int i = 0; i < arraySize; i++) {
            array[i] = nextLong();
        }
        return array;
    }
}