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 , 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 .

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

Constraints:

1<= t <= 100

1<= N, M <= 1000

Output

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