您喜欢在线参加国际象棋锦标赛。
在上一场锦标赛中,您玩了 $$$n$$$ 场比赛。为了解决这个问题,每场国际象棋比赛要么赢要么输(没有平局)。当您输掉一场比赛时,您将获得 $$$0$$$ 积分。当您获胜时,您将获得 $$$1$$$ 或 $$$2$$$ 积分:如果您也赢得了上一场比赛,您将获得 $$$2$$$ 积分,否则您将获得 $$$1$$$ 积分。如果您赢得锦标赛的第一场比赛,您将获得 $$$1$$$ 积分(因为没有“上一场比赛”)。
$$$n$$$ 游戏的结果由长度为 $$$n$$$ 的字符串 $$$s$$$ 表示:如果您赢得了第 $$$i$$$ 游戏,则 $$$s$$$ 的第 $$$i$$$ 个字符为 W;如果您输掉了第 $$$i$$$ 游戏,则 $$$s$$$ 的第 $$$i$$$ 个字符为 L。
锦标赛结束后,您注意到网站上有一个错误,允许您最多更改 $$$k$$$ 游戏的结果(这意味着您最多可以将 $$$k$$$ 次的符号从 L 更改为 W,或将 W 更改为 L)。由于您的唯一目标是提高您的国际象棋等级,因此您决定作弊并使用该错误。
计算以最佳方式作弊可以获得的最高分数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t \le 20,000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n, k$$$ ($$$1\le n\le 100,000$$$, $$$0\le k\le n$$$) – 玩过的游戏数量和可以更改的结果数量。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 W 和 L。如果您赢得了第 $$$i$$$ 场比赛,则 $$$s_i=\,$$$W,如果您输掉了第 $$$i$$$ 场比赛,则 $$$s_i=\,$$$L。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$200,000$$$。
输出
对于每个测试用例,打印一个整数——以最佳方式作弊可以获得的最高分数。
示例
输入 #1
8 5 2 WLWLL 6 5 LLLWWL 7 1 LWLWLWL 15 5 WWWLLLWWWLLLWWW 40 7 LLWLWLWWWLWLLWLWWWLWLLWLLWLLLLWLLWWWLWWL 1 0 L 1 1 L 6 1 WLLWLW
输出 #1
7 11 6 26 46 0 1 6
注意
第一个测试用例的解释。在改变任何结果之前,分数为 $$$2$$$。事实上,你赢了第一场比赛,所以你得到了 $$$1$$$ 分,你也赢得了第三场比赛,所以你又得到了 $$$1$$$ 分(而不是 $$$2$$$ 分,因为你输了第二场比赛)。
作弊的最佳方式是改变第二场和第四场比赛的结果。这样做,您最终会赢得前四场比赛(结果字符串变为 WWWWL)。因此,新分数为$$$7=1+2+2+2$$$:第一场比赛为$$$1$$$分,第二、第三和第四场比赛为$$$2$$$分。
第二个测试用例的解释。在改变任何结果之前,分数为 $$$3$$$。事实上,您赢得了第四场比赛,因此您获得了 $$$1$$$ 分,并且您还赢得了第五场比赛,因此您获得了 $$$2$$$ 分(因为您还赢得了上一场比赛)。
作弊的最佳方法是改变第一、第二、第三和第六场比赛的结果。这样做,您最终会赢得所有游戏(结果字符串变为 WWWWWW)。因此,新分数为 $$$11 = 1+2+2+2+2+2$$$:第一场比赛为 $$$1$$$ 分,所有其他比赛为 $$$2$$$ 分。