長さ $n$ の 2 つの二進文字列 $a$ と $b$ が与えられます。位置の添字は $0$ から $n-1$ までです。

整数の組 $(s,l)$ ($0 \le s,l<n$) に対し、すべての整数 $j$ ($0 \le j<k$) について位置 $(l+j)\bmod n$ にある $k$ 文字を反転して、$a$ から文字列 $a'$ を作ります。

すべての $i$ ($0 \le i<n$) について $a'_i=b_{(i+s)\bmod n}$ が成り立つとき、組 $(s,l)$ は有効です。

有効な組 $(s,l)$ の個数を求めてください。異なる組 $(s,l)$ は、同じ文字列 $a'$ を作る場合も別々に数えます。

入力

各テストファイルには複数のテストケースが含まれます。1 行目にはテストケース数 $T$ ($1 \le T \le 10^4$) が与えられます。その後に各テストケースの記述が続きます。

各テストケースの 1 行目には 2 つの整数 $n$ と $k$ ($2 \le n \le 10^6$, $1 \le k<n$) が与えられます。

2 行目には長さ $n$ の二進文字列 $a$ が与えられます。

3 行目には長さ $n$ の二進文字列 $b$ が与えられます。

すべてのテストケースにわたる $n$ の総和が $10^6$ 以下であることが保証されます。

出力

各テストケースについて、有効な組 $(s,l)$ の個数を表す整数を 1 つ出力してください。

入出力例

入力 1

2
6 2
000000
001100
5 2
01010
11100

出力 1

6
0

注記

1 番目のテストケースで有効な組 $(s,l)$ は $(2,0)$、$(1,1)$、$(0,2)$、$(5,3)$、$(4,4)$、$(3,5)$ です。最後の組では、反転する位置は $5$ と $0$ です。

2 番目のテストケースには有効な組 $(s,l)$ がありません。