字符串匹配是 DNA 序列分析和文本编辑中的一个常见问题，其目的是在一个较长的字符串（称为文本）中找到某个特定字符串（称为模式）出现的位置。在某些情况下，并不要求模式在文本中完全匹配，允许存在微小的差异（由于可能的输入错误）。给定一个模式字符串和一个文本字符串，如果文本 $S$ 中存在一个与模式 $P$ 最多只有一个字符不同的子串，我们就称模式 $P$ 在文本 $S$ 中近似匹配。注意，该子串的长度必须与模式的长度相同。例如，模式 “abb” 在文本 “babc” 中近似匹配，但在 “bbac” 中不匹配。

检查一个模式是否在文本中近似匹配很容易。你的任务是计算长度为 $m$ 的所有文本字符串的数量，使得给定的模式可以在其中近似匹配。为了避免处理大整数，模式和文本均为二进制字符串。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 666$)，表示测试用例的数量。每个测试用例的第一行包含两个整数 $n, m$ ($1 \le n, m \le 40$)，分别表示模式字符串和文本字符串的长度。接下来一行包含一个二进制字符串 $P$，表示模式。注意，其中 $n \ge 16$ 的测试用例最多有 15 个。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

输入 1

5
3 4
110
4 7
1011
2 10
00
7 17
1001110
11 22
11101010001

输出 1

12
104
1023
72840
291544