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$.

见题面

见题面