字符串

题号：NC259247
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一个长度为 $n$ 的只包含字符 $'a','b','c'$ 的字符串，给出一个整数 $k$ ，最多可以对字符串执行 $k$ 次操作。

每次操作选择一个下标 $i\ (1\le i\le n)$ ，将字符串 $[1,i],[i+1,n]$ 反转。

比如 $abcabc$ ，第一次操作选择下标 $3$ ，操作后字符串变成 $cbacba$ ，第二次操作选择下标 $5$ ，操作后字符串变成 $bcabca$ 。

特别的，如果选择了下标 $n$ ，直接将整个字符串反转即可。

问：最多执行 $k$ 次操作（也可以一次都不执行），在完成操作后，字符串的子序列 “ $abc$ ” 的个数最多有多少个？

第一行一个整数 $T\ (1\le T\le10^3)$ ，表示样例的个数。

每个样例包含两行，第一行包含两个整数 $n\ k\ (1\le n\le 3\times10^6,0\le k\le 10^5)$ ，分别表示字符串的长度，操作的次数。

第二行包含一个长度为 $n$ 的字符串 $S$ 。

数据保证 $\sum n\le 1.2\times10^7$ 。

输出  行，每行一个整数，表示第  个字符串经过操作后，最多可以得到子序列 "" 的个数。

示例1

复制

2
7 10
ccaaabc
3 1
aca

复制

9
0

第一个样例：第一次操作选择下标 $5$ ，字符串变成 $aaacccb$ ，第二次操作选择下标 $3$ ，字符串变成 $aaabccc$ ，一共包含 $9$ 个子序列 $abc$ 。

第二个样例无论怎么操作都不包含子序列 $abc$ ，输出 $0$ 。