В ряд стоят $$$n$$$ поросят, пронумерованных слева направо от $$$1$$$ до $$$n$$$. Каждый поросёнок смотрит либо влево, либо вправо.
Два поросёнка $$$x$$$ и $$$y$$$ называются парой свинсторожей, если $$$x \lt y$$$, $$$x$$$ смотрит вправо, а $$$y$$$ смотрит влево.
Дано целое число $$$k$$$ такое, что $$$1 \le k \lt n$$$. Поросёнок в безопасности, если он принадлежит как минимум $$$k$$$ парам свинсторожей.
Ваша задача — сделать так, чтобы все поросята были в безопасности. Для этого можно выбрать любое количество поросят и развернуть их направление (изменить влево на вправо или наоборот).
Найдите минимальное количество поросят, которых нужно развернуть, чтобы каждый поросёнок оказался в безопасности, или сообщите, что это невозможно.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \lt n \le 100$$$), обозначающие количество поросят и количество пар свинсторожей, в которых должен участвовать каждый поросёнок, соответственно.
Во второй строке дана строка $$$s$$$ длины $$$n$$$, состоящая только из символов $$$\mathtt{L}$$$ и $$$\mathtt{R}$$$. Для каждого $$$1 \le i \le n$$$, если $$$s_i= \mathtt{L}$$$, то поросёнок $$$i$$$ смотрит влево; иначе, если $$$s_i= \mathtt{R}$$$, то поросёнок $$$i$$$ смотрит вправо.
Для каждого набора входных данных, если невозможно сделать так, чтобы каждый поросёнок был в безопасности, выведите $$$-1$$$. Иначе выведите минимальное количество поросят, которых нужно развернуть, чтобы каждый поросёнок оказался в безопасности.
43 1LLL4 3LRLR6 2RLLRRL12 4LRLLRRLRLRLR
1-125
В первом наборе входных данных одно из оптимальных решений — развернуть поросёнка $$$1$$$. Теперь и поросёнок $$$1$$$, и поросёнок $$$3$$$ принадлежат паре свинсторожей $$$(1,3)$$$, а поросёнок $$$2$$$ принадлежит паре свинсторожей $$$(1,2)$$$. Каждый поросёнок принадлежит как минимум $$$k=1$$$ паре свинсторожей, следовательно, каждый поросёнок в безопасности.
Во втором наборе входных данных можно доказать, что сделать так, чтобы каждый поросёнок был в безопасности, невозможно.
В третьем наборе входных данных одно из оптимальных решений — развернуть поросят $$$2$$$ и $$$5$$$. Например, поросёнок $$$2$$$ теперь в безопасности, так как он принадлежит и $$$(2,3)$$$, и $$$(2,5)$$$. Поросёнок $$$4$$$ тоже в безопасности, так как он принадлежит и $$$(4,5)$$$, и $$$(4,6)$$$. Остальные поросята тоже в безопасности.
