Problem Description

Yu Peng the Penguin is taking photos with his penguin friends today! Penguins have white bellies and black wings and back, and as penguins are more or less of the same height, the photos taken can be represented as a binary string, where '0' denotes a black pixel and '1' denotes a white pixel.

Yu Peng has taken T photos, where the ith photo is of length Ni. He tells you that in the ith photo, there are at most Ki penguins. Yu Peng recognises a penguin as a contiguous segment of white pixels (penguin with belly facing front), or a contiguous segment of black pixels (penguin with back facing front), both of arbitrary length. However, some naughty penguins faced the camera sideways when the photos were taken, and hence, there may be more than Ki penguins in the ith photo, according to Yu Peng's rules.

Yu Peng is not happy with these naughty penguins and wants to edit the photos. He wonders, for the ith photo, what is the minimum number of pixels that he has to change the colour of, such that he sees at most Ki penguins in the photo.

Input

The first line contains a single integer T, the number of photos.

Then, there are T pairs of lines, each describing a single photo taken.

For the ith pair of lines:

The first line contains two integers Ni and Ki.

The second line contains a binary string of length Ni.

Output

Output T lines. The ith line should contain a binary string of length Ni, describing the ith edited photo, according to Yu Peng's requirements.

If there are several possible optimal edited photos, output any of them.

Limits

Subtask 1 (11%): 1 ≤ KiNi ≤ 10. 1 ≤ ∑ Ni ≤ 5000.

Subtask 2 (24%): 1 ≤ KiNi ≤ 100. 1 ≤ ∑ Ni ≤ 5000.

Subtask 3 (24%): 1 ≤ KiNi ≤ 1000. 1 ≤ ∑ Ni ≤ 50 000.

Subtask 4 (21%): 1 ≤ Ki ≤ 5000. 1 ≤ ∑ Ni ≤ 100 000.

Subtask 5 (20%): 1 ≤ Ki ≤ 200 000. 1 ≤ ∑ Ni ≤ 200 000.

Subtask 6 (0%): Sample Testcases

Sample Testcase 1

Input

3
9 3
000111000
10 3
0111011010
4 4
0001

Output

000111000
0111111000
0001