F. Circular Light Calibration
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two binary strings $$$a$$$ and $$$b$$$ of length $$$n$$$. Their positions are indexed from $$$0$$$ to $$$n-1$$$.

For a pair of integers $$$(s,l)$$$ ($$$0 \le s,l \lt n$$$), construct a string $$$a'$$$ from $$$a$$$ by inverting the $$$k$$$ characters at positions $$$(l+j)\bmod n$$$ for all integers $$$j$$$ ($$$0 \le j \lt k$$$).

The pair $$$(s,l)$$$ is valid if $$$a'_i=b_{(i+s)\bmod n}$$$ for every $$$i$$$ ($$$0 \le i \lt n$$$).

Find the number of valid pairs $$$(s,l)$$$. Different pairs $$$(s,l)$$$ are counted separately, even if they produce the same string $$$a'$$$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \lt n$$$).

The second line contains a binary string $$$a$$$ of length $$$n$$$.

The third line contains a binary string $$$b$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer — the number of valid pairs $$$(s,l)$$$.

Example
Input
2
6 2
000000
001100
5 2
01010
11100
Output
6
0
Note

In the first test case, the valid pairs $$$(s,l)$$$ are $$$(2,0)$$$, $$$(1,1)$$$, $$$(0,2)$$$, $$$(5,3)$$$, $$$(4,4)$$$, and $$$(3,5)$$$. For the last pair, the inverted positions are $$$5$$$ and $$$0$$$.

There is no valid pair $$$(s,l)$$$ in the second test case.