<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.*;import java.util.*;import java.math.*;
public class Main
{
	public void tq()throws Exception
	{
		st=new StringTokenizer(bq.readLine());
		int tq=i();
		sb=new StringBuilder(1000000);
		o:
		while(tq-->0)
		{
			int n=i();
			int m=i();
			char ar[]=s().toCharArray();
			LinkedList<Integer> l=new LinkedList<Integer>();
			for(int x=0;x<n;x++)if(ar[x]=='1')l.add(x);
			if(l.size()==0)sl(new String(ar));
			else
			{
				int v=min(m,l.get(0));
				int i=l.get(0)-1;
				while(v-->0)ar[i--]='1';
				
				v=min(m,n-l.getLast()-1);
				i=l.getLast()+1;
				while(v-->0)ar[i++]='1';
				
				int p=l.remove();
				for(int e:l)
				{
					int d=e-p-1;
					if(d%2==0)
					{
						v=min(d/2,m);
						int ii=p+1;
						int jj=e-1;
						while(v-->0)
						{
							ar[ii++]='1';
							ar[jj--]='1';
						}
					}
					else
					{
						v=min(d/2,m);
						int ii=p+1;
						int jj=e-1;
						while(v-->0)
						{
							if(ii==jj)break;
							ar[ii++]='1';
							ar[jj--]='1';
						}
					}
					p=e;
				}
				sl(new String(ar));
			}
		}
		p(sb);
	}
    
    long mod=1000000007l;int max=Integer.MAX_VALUE,min=Integer.MIN_VALUE;
    long maxl=Long.MAX_VALUE,minl=Long.MIN_VALUE;
    BufferedReader bq=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;StringBuilder sb;
    public static void main(String[] a)throws Exception{new Main().tq();}
    int[] so(int ar[]){Integer r[]=new Integer[ar.length];for(int x=0;x<ar.length;x++)r[x]=ar[x];
    Arrays.sort(r);for(int x=0;x<ar.length;x++)ar[x]=r[x];return ar;}
    long[] so(long ar[]){Long r[]=new Long[ar.length];for(int x=0;x<ar.length;x++)r[x]=ar[x];
    Arrays.sort(r);for(int x=0;x<ar.length;x++)ar[x]=r[x];return ar;}
    char[] so(char ar[])
    {Character r[]=new Character[ar.length];for(int x=0;x<ar.length;x++)r[x]=ar[x];
    Arrays.sort(r);for(int x=0;x<ar.length;x++)ar[x]=r[x];return ar;}
    void s(String s){sb.append(s);}void s(int s){sb.append(s);}void s(long s){sb.append(s);}
    void s(char s){sb.append(s);}void s(double s){sb.append(s);}
    void ss(){sb.append(' ');}void sl(String s){sb.append(s);sb.append("\n");}
    void sl(int s){sb.append(s);sb.append("\n");}
    void sl(long s){sb.append(s);sb.append("\n");}void sl(char s){sb.append(s);sb.append("\n");}
    void sl(double s){sb.append(s);sb.append("\n");}void sl(){sb.append("\n");}
    int l(int v){return 31-Integer.numberOfLeadingZeros(v);}
    long l(long v){return 63-Long.numberOfLeadingZeros(v);}
    int min(int a,int b){return a<b?a:b;}
    int min(int a,int b,int c){return a<b?a<c?a:c:b<c?b:c;}
    int max(int a,int b){return a>b?a:b;}
    int max(int a,int b,int c){return a>b?a>c?a:c:b>c?b:c;}
    long min(long a,long b){return a<b?a:b;}
    long min(long a,long b,long c){return a<b?a<c?a:c:b<c?b:c;}
    long max(long a,long b){return a>b?a:b;}
    long max(long a,long b,long c){return a>b?a>c?a:c:b>c?b:c;}
    int abs(int a){return Math.abs(a);}
    long abs(long a){return Math.abs(a);}
    int sq(int a){return (int)Math.sqrt(a);}long sq(long a){return (long)Math.sqrt(a);}
    long gcd(long a,long b){while(b>0l){long c=a%b;a=b;b=c;}return a;}
    int gcd(int a,int b){while(b>0){int c=a%b;a=b;b=c;}return a;}
    boolean pa(String s,int i,int j){while(i<j)if(s.charAt(i++)!=s.charAt(j--))return false;return true;}
    boolean[] si(int n)
    {boolean bo[]=new boolean[n+1];bo[0]=true;bo[1]=true;for(int x=4;x<=n;x+=2)bo[x]=true;
    for(int x=3;x*x<=n;x+=2){if(!bo[x]){int vv=(x<<1);for(int y=x*x;y<=n;y+=vv)bo[y]=true;}}
    return bo;}long mul(long a,long b,long m) 
    {long r=1l;a%=m;while(b>0){if((b&1)==1)r=(r*a)%m;b>>=1;a=(a*a)%m;}return r;}
    int i()throws IOException{if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    return Integer.parseInt(st.nextToken());}
    long l()throws IOException{if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    return Long.parseLong(st.nextToken());}String s()throws IOException
    {if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());return st.nextToken();}
    double d()throws IOException{if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    return Double.parseDouble(st.nextToken());}void p(Object p){System.out.print(p);}
    void p(String p){System.out.print(p);}void p(int p){System.out.print(p);}
    void p(double p){System.out.print(p);}void p(long p){System.out.print(p);}
    void p(char p){System.out.print(p);}void p(boolean p){System.out.print(p);}
    void pl(Object p){System.out.println(p);}void pl(String p){System.out.println(p);}
    void pl(int p){System.out.println(p);}void pl(char p){System.out.println(p);}
    void pl(double p){System.out.println(p);}void pl(long p){System.out.println(p);}
    void pl(boolean p){System.out.println(p);}void pl(){System.out.println();}
    void s(int a[]){for(int e:a){sb.append(e);sb.append(' ');}sb.append("\n");}
    void s(long a[]){for(long e:a){sb.append(e);sb.append(' ');}sb.append("\n");}
    void s(int ar[][]){for(int a[]:ar){for(int e:a){sb.append(e);sb.append(' ');}sb.append("\n");}}
    void s(char a[]){for(char e:a){sb.append(e);sb.append(' ');}sb.append("\n");}
    void s(char ar[][]){for(char a[]:ar){for(char e:a){sb.append(e);sb.append(' ');}sb.append("\n");}}
    int[] ari(int n)throws IOException
    {int ar[]=new int[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int x=0;x<n;x++)ar[x]=Integer.parseInt(st.nextToken());return ar;}
    int[][] ari(int n,int m)throws IOException
    {int ar[][]=new int[n][m];for(int x=0;x<n;x++){if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int y=0;y<m;y++)ar[x][y]=Integer.parseInt(st.nextToken());}return ar;}
    long[] arl(int n)throws IOException
    {long ar[]=new long[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int x=0;x<n;x++) ar[x]=Long.parseLong(st.nextToken());return ar;}
    long[][] arl(int n,int m)throws IOException
    {long ar[][]=new long[n][m];for(int x=0;x<n;x++)
    {if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int y=0;y<m;y++)ar[x][y]=Long.parseLong(st.nextToken());}return ar;}
    String[] ars(int n)throws IOException
    {String ar[]=new String[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int x=0;x<n;x++) ar[x]=st.nextToken();return ar;}
    double[] ard(int n)throws IOException
    {double ar[]=new double[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int x=0;x<n;x++)ar[x]=Double.parseDouble(st.nextToken());return ar;}
    double[][] ard(int n,int m)throws IOException
    {double ar[][]=new double[n][m];for(int x=0;x<n;x++)
    {if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int y=0;y<m;y++)ar[x][y]=Double.parseDouble(st.nextToken());}return ar;}
    char[] arc(int n)throws IOException{char ar[]=new char[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());
    for(int x=0;x<n;x++)ar[x]=st.nextToken().charAt(0);return ar;}
    char[][] arc(int n,int m)throws IOException{char ar[][]=new char[n][m];
    for(int x=0;x<n;x++){String s=bq.readLine();for(int y=0;y<m;y++)ar[x][y]=s.charAt(y);}return ar;}
    void p(int ar[]){StringBuilder sb=new StringBuilder(2*ar.length);
    for(int a:ar){sb.append(a);sb.append(' ');}System.out.println(sb);}
    void p(int ar[][]){StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
    for(int a[]:ar){for(int aa:a){sb.append(aa);sb.append(' ');}sb.append("\n");}p(sb);}
    void p(long ar[]){StringBuilder sb=new StringBuilder(2*ar.length);
    for(long a:ar){sb.append(a);sb.append(' ');}System.out.println(sb);}
    void p(long ar[][]){StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
    for(long a[]:ar){for(long aa:a){sb.append(aa);sb.append(' ');}sb.append("\n");}p(sb);}
    void p(String ar[]){int c=0;for(String s:ar)c+=s.length()+1;StringBuilder sb=new StringBuilder(c);
    for(String a:ar){sb.append(a);sb.append(' ');}System.out.println(sb);}
    void p(double ar[]){StringBuilder sb=new StringBuilder(2*ar.length);
    for(double a:ar){sb.append(a);sb.append(' ');}System.out.println(sb);}
    void p(double ar[][]){StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
    for(double a[]:ar){for(double aa:a){sb.append(aa);sb.append(' ');}sb.append("\n");}p(sb);}
    void p(char ar[]){StringBuilder sb=new StringBuilder(2*ar.length);
    for(char aa:ar){sb.append(aa);sb.append(' ');}System.out.println(sb);}
    void p(char ar[][]){StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);
    for(char a[]:ar){for(char aa:a){sb.append(aa);sb.append(' ');}sb.append("\n");}p(sb);}
}