B. Посчитай количество пар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кристины есть строка $$$s$$$ длины $$$n$$$, состоящая только из строчных и заглавных латинских букв. За каждую пару из строчной буквы и соответствующей ей заглавной Кристина может получить $$$1$$$ бурль. При этом, пары из символов не могут пересекаться, то есть каждый символ может быть только в одной паре.

Например, если у нее есть строка $$$s$$$ = «aAaaBACacbE», то она может получить бурль за следующие пары символов:

  • $$$s_1$$$ = «a» и $$$s_2$$$ = «A»
  • $$$s_4$$$ = «a» и $$$s_6$$$ = «A»
  • $$$s_5$$$ = «B» и $$$s_{10}$$$ = «b»
  • $$$s_7$$$= «C» и $$$s_9$$$ = «c»

Кристина хочет получить больше бурлей за свою строку, поэтому она собирается совершить над ней не более $$$k$$$ операций. За одну операцию она может:

  • либо выбрать строчный символ $$$s_i$$$ ($$$1 \le i \le n$$$) и сделать его заглавным.
  • либо выбрать заглавный символ $$$s_i$$$ ($$$1 \le i \le n$$$) и сделать его строчным.

Например, при $$$k$$$ = 2 и $$$s$$$ = «aAaaBACacbE» она может совершить одну операцию: выбрать $$$s_3$$$ = «a» и сделать его заглавным. Тогда она получит еще одну пару из $$$s_3$$$ = «A» и $$$s_8$$$ = «a».

Найдите максимальное количество бурлей, которое Кристина может получить за свою строку.

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

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) и $$$k$$$ ($$$0 \le k \le n$$$) — количество символов в строке и максимальное количество операций, которое можно над ней совершить.

Во второй строке каждого набора входных данных записана строка $$$s$$$ длины $$$n$$$, состоящая только из строчных и заглавных латинских букв.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных на отдельной строке выведите ровно одно целое число: максимальное количество бурлей, которое Кристина может получить за строку $$$s$$$.

Пример
Входные данные
5
11 2
aAaaBACacbE
2 2
ab
4 1
aaBB
6 0
abBAcC
5 3
cbccb
Выходные данные
5
0
1
3
2
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных невозможно получить ни одну пару выполнив любое количество операций.