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

Скобочная последовательность — это строка, содержащая только символы «(» и «)». Правильная скобочная последовательность (или, коротко говоря, ПСП) — это скобочная последовательность, которая может быть преобразована в правильное арифметическое выражение путем вставки символов «1» и «+» между исходными символами последовательности. Например:

  • скобочные последовательности «()()» и «(())» являются правильными (возможные выражения: «(1)+(1)» и «((1+1)+1)»);
  • скобочные последовательности «)(», «(» и «)» не являются правильными.

Вам задана строка $$$s$$$, которая является ПСП. К этой строке можно применить любое количество операций. Каждая операция может иметь один из следующих типов:

  1. выбрать некоторый непустой префикс $$$s$$$ и удалить его из $$$s$$$, так что $$$s$$$ все еще остается ПСП. Например, можно применить эту операцию следующим образом: «(())()(())()()» $$$\to$$$ «()()» (первые $$$10$$$ символов были удалены);
  2. выбрать некоторую непрерывную непустую подстроку $$$s$$$ и удалить ее из $$$s$$$, так что $$$s$$$ все еще остается ПСП. Например, можно применить эту операцию следующим образом: «(())()(())()()» $$$\to$$$ «(())()()()» (символы с $$$7$$$-го по $$$10$$$-й были удалены).

Операция $$$2$$$ может быть применена не более $$$k$$$ раз. Посчитайте максимальное количество операций, которые можно применить, пока $$$s$$$ не станет пустой.

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

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

Каждый набор описывается двумя строками. Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$; $$$n$$$ четно) — длина $$$s$$$ и максимальное количество операций типа $$$2$$$, которые можно применить.

Вторая строка содержит $$$s$$$ состоящую из $$$n$$$ символов «(» и «)». Эта строка является ПСП.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
3
12 2
(()())((()))
6 3
()()()
8 1
(((())))
Выходные данные
4
3
2