<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 
/*
    +-----------------------+
    |       CHECKLIST       |
    +-----------------------+
    |1. PIGEONHOLE PRINCIPLE|
    |2. TWO POINTERS        |
    |3. BINARY SEARCH       |
    |4. GREEDY ALGORITHM    |
    |5. DYNAMIC PROGRAMMING |
    |6. GRAPH               |
    |7. SEGMENT TREE        |
    +-----------------------+
*/
#include<bits/stdc++.h>
using namespace std;
void read() {}
template<class T, class... Arg>
void read(T &x, Arg&&... args) {
    cin >> x;
    read(args...);
}
void print_err() {
    cerr << "\n";
}
template <class T, class... Arg>
void print_err(T x, Arg&&... args) {
    cerr << x << " ";
    print_err(args...);
}
template<class T>
void print_container(T &cont) {
    for (auto iter : cont) {
        cerr << iter << " ";
    }
    cerr << "\n";
}
template<class T>
void print_container_pair(T &cont) {
    for (auto iter : cont) {
        cerr << iter.first << " " << iter.second << "\n";
    }
    cerr << "\n";
}
template<class T>
void print_container_map(T &cont) {
    for (auto iter : cont) {
        cerr << iter.first << " " << iter.second << "\n";
    }
    cerr << "\n";
}
inline void kick_temp(int test) {
    cout << "Case #" << test << ": ";
}
#ifdef local
#define debug(...) print_err(__VA_ARGS__)
#define debug_vect(container) print_container(container)
#define debug_vect_pair(container) print_container_pair(container)
#define debug_map(container) print_container_map(container)
#else
#define debug(...)
#define debug_c(container)
#endif
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define test_case int test_cases;\
                cin>>test_cases;\
                for(i = 1; i<=test_cases;++i)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define mod 1000000007
#define int long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define mii map<int,int>
#define miirev map<int,int,greater<int>>
#define ps(x,y) fixed<<setprecision(y)<<x//it will give upto y decimal places
#define w(t) int t;cin>>t;while(t--)
#define fo(i,n) for(int i=0;i<n;++i)
#define foab(i,a,b) for(int i=a;i<b;++i)
#define foba(i,b,a) for(int i=b;i>=a;--i)
#define sz(c) c.size()
#define inp cin>>
#define pr cout<<
#define pqb priority_queue<int>//max heap
#define pqs priority_queue<int,vi,greater<int>>//min heap
#define mk(arr,n,type) type *arr=new type[n];
#define all(A) (A).begin(),(A).end()
#define fastio ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define mem(a,val) memset(a,val,sizeof(a))
#define rev_sort(...) sort(__VA_ARGS__);reverse(__VA_ARGS__);
#define br cout<<"\n"
#define sp cout<<" "
#define pr cout<<
template<class T>
void debug_arr(T arr, int st, int en) {
    foab(i, st, en) {
        cerr << arr[i] << " ";
    }
    cerr << endl;
}
template<class T>
void read_arr(T arr, int n) {
    fo(i, n) {
        cin >> arr[i];
    }
}
template<class T>
void read_c(T &arr, int n) {
    fo(i, n) {
        cin >> arr[i];
    }
}
void CP() {
    fastio
#ifdef local
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
    return;
}
char* stringTOCharArray(string str) {
    int n = str.length();
    mk(ch, n + 1, char);
    strcpy(ch, str.c_str());
    return ch;
}
string intostring(int n) {
    return to_string(n);
}
int stringtoint(string str) {
    return stol(str);
}
int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
void preprocessing() {
    return ;
}
vi d4x {0, 0, 1, -1};
vi d4y{ -1, 1, 0, 0};
vi d8x{0 , 0, 1, -1, 1, 1, -1, -1};
vi d8y{1, -1, 0, 0, -1, 1, 1, -1};
void solve(int faltu) {
    debug("<------------------->");
    int n,m;
    read(n,m);
    string str;
    read(str);
    int oneone=0;
    fo(i,n){
        if(str[i]=='1'){
            oneone++;
        }
    }
    if(oneone==0){
        pr str;
        br;
        return;
    }
    fo(i,m){
        vi tempvect;
        fo(j,n){
            if(j==0){
                if(str[0]=='0' and str[1]=='1') {
                    tempvect.pb(j);
                    // j++;
                }
                continue;
            }
            if(j==n-1){
                if(str[n-1]=='0' and str[n-2]=='1'){
                    tempvect.pb(j);
                }
                continue;
            }
            if(str[j]=='0'){
                if((str[j-1]=='1' and str[j+1]=='0') or (str[j-1]=='0' and str[j+1]=='1')){
                    tempvect.pb(j);
                    // j++;
                }
            }
        }
        // debug_vect(tempvect);
        fo(j,sz(tempvect)){
            str[tempvect[j]]='1';
        }
        if(sz(tempvect)==0){
            break;
        }
    }
    pr str;
    br;
    return ;
}
int32_t main() {
    CP();
    int i = 1;
    preprocessing();
    test_case
    solve(i);
    return 0;
}