Again XOR problem

 You may have solved a lot of problems related to XOR and we are sure that you liked them, so here is one more problem for you.

You are given a binary string S$S$ of length N$N$. Let string T$T$ be the result of taking the XOR of all substrings of size K$K$ of S$S$. You need to find the number of 1 bits in T$T$.

Note:

• A substring is a continuous part of string which can be obtained by deleting some (may be none) character's from the beginning and some (may be none) character's from the end.
• XOR of many similar-sized strings is defined here.

Input Format

• The first line of the input contains an integer T$T$ - the number of test cases. The test cases then follow.
• The first line of each test case contains two integers N$N$ and K$K$.
• The second line of each test case contains a binary string S$S$ of size N$N$.

Output Format

For each test case, output on a single line number of 1 bits in the XOR of all substrings of size K$K$ of S$S$.

Constraints

• 1≤T≤10$1\le T\le 10$
• 1≤K≤N≤2⋅105$1\le K\le N\le 2\cdot {10}^5$
• |S|=N$|S|=N$
• S$S$ only contains characters 0 and 1.

Sample Input 1 

4
4 1
1010
4 2
1001
4 3
1111
4 4
0110

Sample Output 1 

0
2
0
2

Explanation

• Test case 1$1$: All 1$1$-sized substrings of S$S$ are:
  • 0
  • 1
  • 1
  • 0

The XOR of these strings is 0, therefore the number of 1 bits is 0$0$.

• Test case 2$2$: All 2$2$-sized substrings of S$S$ are:
  • 10
  • 00
  • 01

The XOR of these strings is 11, therefore the number of 1 bits is 2$2$.

• Test case 3$3$: All 3$3$-sized substrings of S$S$ are:
  • 111
  • 111

The XOR of these strings is 000, therefore the number of 1 bits is 0$0$.

• Test case 4$4$: All 4$4$-sized substrings of S$S$ are:
  • 0110

The XOR of these strings is 0110, therefore the number of 1 bits is 2$2$.