Mr. X and His String

Mr. X found a string of length $N$, which contains only 0 and 1. He calculates the value of a string by counting the number of 1 in it.

He decided to play with this string. He will randomly pick a segment $(l, r)$ from the string and toggle all the characters from $l$ to $r$ (toggle means 0 to 1, and 1 to 0). He will do this operation $M$ times.

But he has a lot of works to do and doesn't have enough time to perform this $M$ operations. So he is interested to know the expected value of the string, after performing $M$ operations. Assume that probability of each segment being selected is same.

Input

First contains an integer $t$ ($1 \le t \le 100$), denotes the number of test cases.

Each of the next two lines describe a test case.

First line of each test case contains two integer $N$ and $M$ ($1 \le N, M \le 1000$).

Second line of each test case contains a binary string of $N$ length.

Output

For each test case, print the expected value of the string after performing $M$ operation in a single line.

If the answer is

then print it as

Sample

Input	Output
1 2 1 00	333333337