Chef has binary string A of length N. He constructs a new binary string B by concatenating M copies of A together. For example, if $A = \texttt{$"10010"}, M = 3, then $B = \texttt{$"100101001010010"}.

Chef calls an index i (1 ≤ i ≤ $N \cdot M) *good*$ if:
pref_{i} = suf_{i + 1}.

Here, $pref_{j} = B_{1} + B_{2} + \ldots + B_{j}$ and
$suf_{j} = B_{j} + B_{j + 1} + \ldots + B_{N \cdot M} ($Note that $suf_{N \cdot M + 1} = 0$ by definition)

Chef wants to find the number of good indices in B. Can you help him do so?

------ Input Format ------

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains two space-separated integers N and M — the length of the binary string A and the number of times A is concatenated to form
• The second line of each test case contains a binary string A of length N containing 0s and 1s only.

------ Output Format ------

For each test case, output the number of good indices in B.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 10^{5}$
$A$ is a binary string, i.e, contains only the characters $0$ and $1$.
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.
- The sum of $M$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
3
2 2
00
2 4
11
3 3
101

----- Sample Output 1 ------
4
1
2

----- explanation 1 ------
Test case $1$: $B = \texttt{"0000"}$. In this string, all the indices are good.

Test case $2$: $B = \texttt{"11111111"}$. In this string, only $i = 4$ is good.

Test case $3$: $B = \texttt{"101101101"}$. In this string, $i = 4$ and $i = 5$ are good.

见题面

见题面