题目描述

招堤位于安龙县城东北，始建于清康熙三十三年，现为国家4A级旅游景区及省级文物保护单位。清道光年间，兴义府知府张锳每晚派差役为挑灯夜读的学子添加桐油，并高唱“府台大人给相公添油啰！”。这被认为是汉语“加油”一词的起源之一。如今，招堤灯会延续着这段历史文脉。

灯会开幕前，工匠要按照灯谱校准一圈红白两色的排灯。他可以将连续若干盏灯的颜色反转，再转动整个灯盘，使排灯与灯谱吻合。工匠想知道，一共有多少种不同的校准方式。

形式化地，给定两个长度为 $n$ 的 01 串 $a$ 和 $b$。字符串中字符的下标为 $0$ 到 $n-1$。

对于一对整数 $(s,l)$ ($0 \le s,l<n$)，先将 $a$ 中位置为 $(l+j)\bmod n$ 的这 $k$ 个字符取反，其中 $j$ 为满足 $0 \le j<k$ 的所有整数，由此得到字符串 $a'$。如果对于每个整数 $i$ ($0 \le i<n$)，均有 $a'_i=b_{(i+s)\bmod n}$，则称 $(s,l)$ 是合法的。

求合法的 $(s,l)$ 对的数量。即使不同的 $(s,l)$ 对产生了相同的字符串 $a'$，它们也被视为两种不同的方案。

输入格式

每个测试文件包含多组测试数据。第一行包含测试数据的组数 $T$ ($1 \le T \le 10^4$)。每组测试数据的格式如下。

每组测试数据的第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 10^6$, $1 \le k<n$)。

第二行包含一个长度为 $n$ 的 01 串 $a$。

第三行包含一个长度为 $n$ 的 01 串 $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)$ 对。