Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

B. Шахматный мошенник
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам нравится играть в шахматные турниры онлайн.

В своем последнем турнире вы сыграли $$$n$$$ игр. В этой задаче, каждая шахматная партия заканчивается либо победой, либо поражением (ничьих не бывает). Когда вы проигрываете партию, вы получаете $$$0$$$ очков. Когда вы выигрываете, вы получаете $$$1$$$ или $$$2$$$ очка: если вы выиграли и предыдущую партию, вы получаете $$$2$$$ очка, в противном случае вы получаете $$$1$$$ очко. Если вы выиграли самую первую игру турнира, вы получаете $$$1$$$ очко (так как не существует "предыдущей игры").

Итоги $$$n$$$ игр записываются в строку $$$s$$$ длиной $$$n$$$: $$$i$$$-й символ $$$s$$$  — W, если вы выиграли $$$i$$$-ю игру, и L, если вы проиграли $$$i$$$-ю игру.

После окончания турнира вы замечаете баг на сайте, который позволяет вам изменить результат не более $$$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$$$) — количество сыгранных партий и количество исходов, которые можно изменить.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длиной $$$n$$$, содержащую только символы W и L. Если вы выиграли $$$i$$$-ю игру, то $$$s_i=\,$$$W, если вы проиграли $$$i$$$-ю игру, то $$$s_i=\,$$$L.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превысит $$$200,000$$$.

Выходные данные

Для каждого теста выведите одно целое число  — максимальное количество очков, который вы можете получить, обманув оптимальным способом.

Пример
Входные данные
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
Выходные данные
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$$$ очка за все остальные партии.