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.
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.
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
1 2 1 00