Description

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<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<k$).

The pair $(s,l)$ is valid if $a'_i=b_{(i+s)\bmod n}$ for every $i$ ($0 \le i<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<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)$.

Sample Input 1

2
6 2
000000
001100
5 2
01010
11100

Sample Output 1

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.