{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003eString matching, a common problem in DNA sequence analysis and text editing, is to find the occurrences of one certain string (called pattern) in a larger string (called text). In some cases, the pattern is not required to be exactly in the text, and minor differences are acceptable (due to possible typing mistakes). When given a pattern string and a text string, we say pattern P is approximately matched within text S, if there is a substring of S which is at most one letter different from P. Note that the length of this substring and the pattern must be identical. For example, pattern \"abb\" is approximately matched in text \"babc\" but not matched in \"bbac\".\u003c/p\u003e \n \u003cp\u003eIt is easy to check if a pattern is approximately matched in a text. So your task is to count the number of all text strings of length m in which the given pattern can be approximately matched, and both of the patterns and texts are binary strings in order not to handle big integers.\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThe first line of input is a single integer T (1 ≤ T ≤ 666), the number of test cases. Each test case begins with a line of two integers n,m (1 ≤ n,m ≤ 40), denoting the length of pattern string and text string. Then a single line of binary string P follows, which denotes the pattern. Note that there will be at most 15 test cases in which n ≥ 16.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003eFor each test case, output a single line with one integer, representing the answer.\u003c/p\u003e \n \u003c/div\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e5\r\n3 4\r\n110\r\n4 7\r\n1011 \r\n2 10\r\n00\r\n7 17\r\n1001110\r\n11 22\r\n11101010001\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e12\r\n104\r\n1023\r\n72840\r\n291544\u003c/pre\u003e \n "}}]}