P16122 [USTCPC 2026] Junction and Run Code

克露丝卡尔酱今天也被奇怪的字符串难题困扰着！ 身旁的后辈歪着头：“前辈不是最擅长这种问题吗？” 克露丝卡尔酱的脸微微发红：“哼、哼！当然难不倒我啦！”

字符串的 **游程（run）** 定义为仅包含一种字符且不可扩展的非空子串，例如 `aabaa` 共有三个游程，分别为 `aa`、`b`、`aa`。 给定长度为 $n$ 的字符串，你可以将其切成三个非空字符串并以任意顺序重新拼接为一个字符串，计算有多少种不同的方案可以使得新字符串的游程数量为 $k$。 注意：两个方案不同当且仅当切分位置不同或拼接顺序不同，拼接顺序共有 $6$ 种。

**本题有多组测试数据。** 首先输入一行，包含一个整数 $T$ ($1\le T\le 10^5$)，表示测试数据组数。 每组数据首先输入一行，包含两个整数，分别表示字符串长度 $n$ ($3\le n\le 10^5$) 和游程数量 $k$ ($1\le k\le n$)。 之后输入一行，包含一个长度为 $n$ 的字符串，字符串仅包含小写英文字母。 保证 $\sum n\le 10^5$。

输出 $T$ 行，每行一个整数，表示方案数。

在第一组样例中，将字符串切成 `abb`、`cc`、`aba` 三段，把第三段放到最前面，得到 `abaabbcc`，游程数量为 $5$，满足要求。