Pasha has a string A, of length N, and an integer K.

Consider a string B of length M. A character c in string B is said to be *good*, if the difference between the total occurrences of c and the total remaining characters in B (other than c), is equal to K.  

Formally, if \texttt{freq(c, B)} denotes the frequency of character c in string B of length M, then, the following condition should hold true for c to be *good*: 
\texttt{freq(c, B)} - (M - \texttt{freq(c, B)}) = 2\cdot \texttt{freq(c, B)} - M = K

Pasha ordered you to find the sum of count of *good* characters across all substrings of string A.

Note that a substring is obtained by deleting some (possibly zero) characters from the beginning of the string and some (possibly zero) characters from the end of the string.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and K — the length of string A and an integer as defined in statement, respectively.
- The second line contains a string A consisting of N lowercase english alphabets.

------ Output Format ------ 

For each test case, output the sum of count of *good* characters across all substrings of string A.

------ Constraints ------ 

$1 ≤ T ≤ 10^{2}$
$1 ≤ N ≤ 10^{5}$
$-10^{3} ≤ K ≤ 10^{3}$
$A$ contains lowercase english alphabets only.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
3
4 0
abcd
4 -1
abac
3 1
aab

----- Sample Output 1 ------ 
6
4
4
----- explanation 1 ------ 
Test case $1$:  Consider all the substrings of $A$:
- For substrings of length $1$, for each character, the value of $2\cdot$ $\texttt{freq(c, B)} - M = 2\cdot 1 - 1 = 1 \neq K$.
- For substrings of length $3$, for each character, the value of $2\cdot$ $\texttt{freq(c, B)} - M = 2\cdot 1 - 3 = -1 \neq K$.
- For substring of length $4$, for each character, the value of $2\cdot$ $\texttt{freq(c, B)} - M = 2\cdot 1 - 4 = -2 \neq K$.
- In the substring $ab$, for both characters $a$ and $b$, the frequency is $1$ and $2\cdot 1 - 2 = 0$. The same satisfies for both characters of substring $bc$ and substring $cd$.

Thus, each substring of length $2$ has $2$ *good* characters each. The sum of count of good characters is $2+2+2 = 6$.

Test case $2$:  In this case, only the substrings of length $3$ have *good* characters:
- Consider $B$ as $aba$. Here $b$ is a *good* character, as $2\cdot$ $\texttt{freq(b, B)} - M = 2\cdot 1 - 3 = -1$.
- Consider $B$ as $bac$. Here, all characters are good characters since the frequency is $1$ for all characters and $2\cdot 1 - 3 = -1$.

The sum of count of good characters is $1+3 = 4$.

Test case $3$: In this case,
- All the substrings of length $1$ have *good* characters.
- Consider $B$ as $aab$. Here $a$ is a *good* character, as $2\cdot$ $\texttt{freq(a, B)} - M = 2\cdot 2 - 3 = 1$.

The sum of count of good characters is $3+1 = 4$.

Difficulty: VERY_HARD
Tags: Data structures

Range queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	assert len(s) == n
	ct = 0
	for c in set(s):
		rts = {0: 1}
		rt = 0
		for d in s:
			rt += 1 if c == d else -1
			ct += rts.get(rt - k, 0)
			rts[rt] = rts.get(rt, 0) + 1
		if 0 < -k <= n:
			char_ct = s[:-k].count(c)
			if char_ct == 0:
				ct -= 1
			for i in range(-k, n):
				if s[i] == c:
					char_ct += 1
				if s[i + k] == c:
					char_ct -= 1
				if char_ct == 0:
					ct -= 1
	print(ct)


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input()).split())

def solve():
	(n, k) = m_int()
	text = input().strip()
	acc = 0
	for c in set(text):
		counts = defaultdict(int)
		counts[0] = 1
		score = 0
		for x in text:
			if x == c:
				score += 1
			else:
				score -= 1
			acc += counts[score - k]
			counts[score] += 1
		if 0 < -k <= n:
			c_cnt = 0
			cumul = [0]
			for x in text:
				if x == c:
					c_cnt += 1
				cumul.append(c_cnt)
			i = 0
			while i - k <= n:
				if cumul[i] == cumul[i - k]:
					acc -= 1
				i += 1
	print(acc)

def main():
	n_cases = r_int()
	for _ in range(n_cases):
		solve()
main()


import string
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	for c in string.ascii_lowercase:
		(mp, pref) = ({}, 0)
		to_insert = [1]
		for i in range(n):
			if s[i] == c:
				pref += 1
				for x in to_insert:
					if x in mp:
						mp[x] += 1
					else:
						mp[x] = 1
				to_insert.clear()
			if 2 * pref - i - k in mp:
				ans += mp[2 * pref - i - k]
			to_insert.append(2 * pref - i)
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	s = input()
	az = ''.join([chr(c) for c in range(97, 97 + 26)])
	res = 0
	for c in range(26):
		m = {}
		add = [1]
		val = 1
		for i in range(N):
			if s[i] == az[c]:
				val += 2
				for x in add:
					m[x] = m.get(x, 0) + 1
				add = []
			val -= 1
			if val - K in m.keys():
				res += m[val - K]
			add.append(val)
	print(res)


def solve(n, k, string, ans):
	for c in set((i for i in string)):
		(dictionary, freq, lst) = ({}, 0, [1])
		for i in range(n):
			if string[i] == c:
				freq += 1
				for x in lst:
					if x in dictionary:
						dictionary[x] += 1
					else:
						dictionary[x] = 1
				lst.clear()
			if 2 * freq - i - k in dictionary:
				ans += dictionary[2 * freq - i - k]
			lst.append(2 * freq - i)
	return ans
for _ in range(int(input())):
	print(solve(*map(int, input().split()), input(), 0))


t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = input()
	res = 0
	for i in range(26):
		d = dict()
		d[0] = 1
		f = 0
		for j in range(n):
			if ord(a[j]) - ord('a') == i:
				f += 1
			k1 = 2 * f - (j + 1)
			di = k1 - k
			if d.get(di, 0) != 0:
				res += d[di]
			if d.get(k1, 0) == 0:
				d[k1] = 1
			else:
				d[k1] += 1
		d.clear()
	if k < 0:
		l = -1 * k
		ans = 0
		for i in range(26):
			(f, r, fr) = (0, 0, 0)
			while r < l:
				if ord(a[r]) - ord('a') == i:
					fr += 1
				r += 1
			while r <= n:
				if fr == 0:
					ans += 1
				if r < n:
					if ord(a[r]) - ord('a') == i:
						fr += 1
					if ord(a[f]) - ord('a') == i:
						fr -= 1
				r += 1
				f += 1
		res -= ans
	print(res)
	t -= 1