길이가 $n$인 두 이진 문자열 $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)$의 개수를 구하여라. 같은 문자열 $a'$을 만들더라도 서로 다른 쌍 $(s,l)$은 각각 따로 센다.

입력

각 테스트 파일에는 여러 테스트 케이스가 있다. 첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 10^4$)가 주어진다. 이어서 테스트 케이스의 설명이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n$과 $k$ ($2 \le n \le 10^6$, $1 \le k<n$)가 주어진다.

두 번째 줄에는 길이가 $n$인 이진 문자열 $a$가 주어진다.

세 번째 줄에는 길이가 $n$인 이진 문자열 $b$가 주어진다.

모든 테스트 케이스에 대한 $n$의 합은 $10^6$을 넘지 않음이 보장된다.

출력

각 테스트 케이스마다 유효한 쌍 $(s,l)$의 개수를 나타내는 정수 하나를 출력한다.

예제

입력 1

2
6 2
000000
001100
5 2
01010
11100

출력 1

6
0

참고

첫 번째 테스트 케이스에서 유효한 쌍 $(s,l)$은 $(2,0)$, $(1,1)$, $(0,2)$, $(5,3)$, $(4,4)$, $(3,5)$이다. 마지막 쌍에서는 위치 $5$와 $0$이 반전된다.

두 번째 테스트 케이스에는 유효한 쌍 $(s,l)$이 없다.