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

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

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

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

Дана правильная скобочная последовательность. За один ход вы можете удалить пару соседних скобок такую, что левая скобка открывающая, а правая — закрывающая. Затем склеить полученные части, не изменяя порядка. Стоимость такого хода равна количеству скобок справа от правой скобки из этой пары.

Стоимость правильной скобочной последовательности равна наименьшей суммарной стоимости ходов, необходимых, чтобы сделать последовательность пустой.

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

  • вытащить скобку из последовательности и вставить ее в любую позицию (между двух скобок, в начало или в конец; возможно, туда же, где она и была).

После всех действий скобочная последовательность должна быть правильной. Какая наименьшая стоимость полученной правильной скобочной последовательности?

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

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

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

Во второй строке записана непустая скобочная последовательность, она состоит только из символов '(' и ')'.

Суммарная длина скобочных последовательностей по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
7
0
()
0
(())
1
(())
5
()
1
(()()(()))
2
((())()(()())((())))
3
((())()(()())((())))
Выходные данные
0
1
0
0
1
4
2