Se te dan dos cadenas binarias $a$ y $b$ de longitud $n$. Sus posiciones se indexan desde $0$ hasta $n-1$.

Para un par de enteros $(s,l)$ ($0 \le s,l<n$), construye una cadena $a'$ a partir de $a$ invirtiendo los $k$ caracteres en las posiciones $(l+j)\bmod n$ para todos los enteros $j$ ($0 \le j<k$).

El par $(s,l)$ es válido si $a'_i=b_{(i+s)\bmod n}$ para todo $i$ ($0 \le i<n$).

Halla el número de pares válidos $(s,l)$. Los distintos pares $(s,l)$ se cuentan por separado, incluso si producen la misma cadena $a'$.

Entrada

Cada archivo de prueba contiene varios casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 10^4$). A continuación se describen los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $k$ ($2 \le n \le 10^6$, $1 \le k<n$).

La segunda línea contiene una cadena binaria $a$ de longitud $n$.

La tercera línea contiene una cadena binaria $b$ de longitud $n$.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime un único entero: el número de pares válidos $(s,l)$.

Ejemplos

Entrada 1

2
6 2
000000
001100
5 2
01010
11100

Salida 1

6
0

Nota

En el primer caso de prueba, los pares válidos $(s,l)$ son $(2,0)$, $(1,1)$, $(0,2)$, $(5,3)$, $(4,4)$ y $(3,5)$. Para el último par, las posiciones invertidas son $5$ y $0$.

No hay ningún par válido $(s,l)$ en el segundo caso de prueba.