It's time for Jon Snow to gather an army to fight against the Night King. So, he proposes Khaleesi to join the army. But, Khaleesi is not interested in Jon's proposal and it is only after Tyrion's involvement that she gets ready to help Jon. But, before helping him she wants to make sure that Jon is eligible for her help and thus, she decides to test his knowledge. She gave Jon a string 'S' of length 'N' consisting of only '0's and '1's. She wants him to convert the string such that it contains only '0's and he is permitted to do the following operation any number of times :

He can select a substring of atmost 'K' length and flip the characters present in that substring (i.e. '0' becomes '1' and '1' becomes '0').

His task is to minimize the number of operations. Jon is not so good with binary numbers so he wants you to help him out.

Constraints:

1<=T<=100
1<=N<=100000
1<=K<=N
S will contain only '0's and '1's.

Input:

First line will contain an integer T denoting number of testcases. Each testcase consists of two lines. First line contains two integers N and K, denoting the length of string and length of maximum allowed substring you can choose. Second line contains the string S.

Output:

For each testcase print a single integer which denotes the minimum number of operations you need to perform.