E. Toggle the Streetlights
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Metropolitan University campus has a long street with $$$n$$$ streetlights arranged in a row, numbered from $$$1$$$ to $$$n$$$. Each streetlight is either on (represented by $$$1$$$) or off (represented by $$$0$$$).

The streetlights have a peculiar automatic control system. Every minute, the system updates all streetlights simultaneously according to the following rule:

For a streetlight at position $$$i$$$ (where $$$1 \le i \le n$$$), we define its neighbors as all positions $$$j$$$ such that $$$|i - j| = 1$$$ and $$$1 \le j \le n$$$.

A streetlight at position $$$i$$$ (where $$$1 \le i \le n$$$) toggles its state (on $$$\to$$$ off or off $$$\to$$$ on) if and only if it has exactly two neighbors and both of them were on in the previous minute.

You are given the initial state of all streetlights. Your task is to determine the state of all streetlights after exactly $$$k$$$ minutes.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.

Each test case consists of two lines:

  • The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^9$$$) — the number of streetlights and the number of minutes, respectively.
  • The second line contains a binary string $$$s$$$ of length $$$n$$$ — the initial state of the streetlights, where $$$s_i = 1$$$ means the $$$i$$$-th streetlight is on, and $$$s_i = 0$$$ means it is off.

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

Output

For each test case, print a single line containing a binary string of length $$$n$$$ — the state of the streetlights after $$$k$$$ minutes.

Example
Input
1
5 1
01010
Output
01110