Background

Today, Cruskal-chan is once again troubled by a strange string problem.

A junior next to her tilts their head: “Aren’t you the best at this kind of problem, senior?”

Cruskal-chan blushes slightly: “Hmph, hmph! Of course it can’t stump me!”

Problem Description

A run of a string is defined as a non-empty substring that contains only one character and cannot be extended. For example, aabaa has three runs: aa, b, aa.

Given a string of length $n$, you may cut it into three non-empty strings and then concatenate them in any order to form a new string. Compute how many different plans can make the number of runs in the new string equal to $k$.

Note: Two plans are different if and only if the cut positions are different or the concatenation order is different. There are $6$ possible concatenation orders.

Input Format

This problem contains multiple test cases.

First, input one line containing an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.

For each test case, first input one line containing two integers, which are the string length $n$ ($3 \le n \le 10^5$) and the number of runs $k$ ($1 \le k \le n$).

Then input one line containing a string of length $n$, consisting only of lowercase English letters.

It is guaranteed that $\sum n \le 10^5$.

Output Format

Output $T$ lines, each containing one integer, the number of plans.

2
8 5
abbccaba
3 1
abc

45
0

Hint

In the first sample, cut the string into three parts: abb, cc, aba. Move the third part to the front to get abaabbcc. The number of runs is $5$, which satisfies the requirement.

Translated by ChatGPT 5