E. Что говорит корова?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
О, му, му, му, я обычно так и говорю!
— корова Бесси

Бесси даёт вам правильную скобочную последовательность (ПСП)$$$^{\text{∗}}$$$ длины $$$n$$$ и целое число $$$k$$$.

За одну операцию можно сделать следующее:

  • Выбрать индекс $$$i$$$ ($$$1 \le i \lt n$$$), для которого $$$s_i s_{i+1} = \mathtt{()}$$$.
  • Обозначить через $$$s'$$$ строку, полученную после удаления этих двух символов из $$$s$$$.
  • Присвоить $$$s := \mathtt{(} + s' + \mathtt{)}$$$.

Эту операцию можно выполнить не более $$$k$$$ раз (возможно, ни разу). Можно доказать, что после каждой такой операции $$$s$$$ остаётся ПСП.

Счётом ПСП называется максимальное число подряд идущих открывающих скобок «$$$\texttt{(}$$$» в строке. Например, счёт строки «$$$\texttt{(())((())())}$$$» равен $$$3$$$.

Ваша задача — найти максимальный возможный счёт, который можно получить, выполнив не более $$$k$$$ операций над данной строкой.

$$$^{\text{∗}}$$$Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставляя символы $$$1$$$ и $$$+$$$ между исходными символами последовательности. Например:

  • скобочные последовательности $$$\texttt{()()}$$$ и $$$\texttt{(())}$$$ являются правильными (получаются выражения $$$\texttt{(1)+(1)}$$$ и $$$\texttt{((1+1)+1)}$$$);
  • скобочные последовательности $$$\texttt{)(}$$$, $$$\texttt{(}$$$ и $$$\texttt{)}$$$ не являются правильными.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2\le n \le 4 \cdot 10^5$$$, $$$0 \le k \le \frac{n}{2}$$$) — длину ПСП и максимальное число операций, которые можно выполнить.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов «$$$\texttt{(}$$$» и «$$$\texttt{)}$$$», — данную ПСП.

Гарантируется, что $$$s$$$ является правильной скобочной последовательностью, а сумма $$$n$$$ по всем наборам входных данных не превышает $$$4 \cdot 10^5$$$.

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

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

Пример
Входные данные
9
2 0
()
4 1
(())
6 2
()()()
8 1
()((()))
8 3
(()())()
12 4
((()())())()
16 1
()(((()((())))))
22 1
((((()()(())((()))))))
28 0
(((()(((())()((())))())))())
Выходные данные
1
2
3
4
4
6
6
6
4
Примечание

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

В третьем наборе входных данных можно выбрать индекс $$$i = 1$$$, после выполнения операции получится $$$s = $$$ «$$$\texttt{(()())}$$$». Затем можно выбрать индекс $$$i = 4$$$, после чего получится $$$s = $$$ «$$$\texttt{((()))}$$$». Было выполнено $$$2$$$ операции и получен счёт $$$3$$$, который является максимально возможным.

В седьмом наборе входных данных можно выбрать индекс $$$i = 6$$$, после выполнения операции получится $$$s = $$$ «$$$\texttt{(()(((((()))))))}$$$», счёт этой строки равен $$$6$$$. Можно доказать, что получить счёт больше $$$6$$$ невозможно.