解题思路

• 题意：给长度为 n 的数字串 s（只含 '0'~'9'），给定一个偶数 k。若某个长度为 k 的子串的前 k/2 个数字之和等于后 k/2 个数字之和，则该子串为“幸运子串”。统计所有幸运子串个数。

• 算法：前缀和 + 滑动窗口 将字符转为数字，建立前缀和数组 pre[i] 表示前 i 个数字之和。任意窗口 [l, l+k-1]：

  • 前半和 sum1 = pre[l+k/2] - pre[l]
  • 后半和 sum2 = pre[l+k] - pre[l+k/2]
  • 若 sum1 == sum2，答案加一。

题目内容

给定一个仅包含数字字符的字符串$s$，长度为$n$ 。又给定一个偶数$k$ ，满足$2≤k≤n$ 。

我们称字符串$s$中所有长度为$k$ 的子串为幸运子串，当且仅当该子串的前$k/2$个字符对应的数字之和等于后$k/2$个字符对应的数字之和。

请计算并输出字符串$s$中幸运子串的总数。

【名词解释】

• 子串：从字符串中连续选取一段字符（可以是整个字符串，也可以是空串）得到的新字符串；

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$t(1＜t＜10^4)$代表测试用例数。

每组测试数据描述如下：

• 在一行上输入两个整数$n,k$ ($2≤n≤10^6$；$2≤k≤n$；$k$为偶数)；
• 在一行上输入一个长度为$n$ 、仅由数字字符 "$0$" 到 "$9$" 构成的字符串 。

除此之外，保证所有测试用例中$n$ 的总和不超过 $10^6$。

输出描述

对于每个测试用例，新起一行，输出一个整数，表示字符串 $s$中幸运子串的数量。

样例1

输入

2
4 2
1122
6 4
121212

输出

2
3