Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:
Дана правильная скобочная последовательность. За один ход вы можете удалить пару соседних скобок такую, что левая скобка открывающая, а правая — закрывающая. Затем склеить полученные части, не изменяя порядка. Стоимость такого хода равна количеству скобок справа от правой скобки из этой пары.
Стоимость правильной скобочной последовательности равна наименьшей суммарной стоимости ходов, необходимых, чтобы сделать последовательность пустой.
На самом деле, никаких скобок вы не удаляете. Вместо этого вам дана правильная скобочная последовательность и целое число $$$k$$$. Вы можете проделать следующее действие не больше $$$k$$$ раз:
После всех действий скобочная последовательность должна быть правильной. Какая наименьшая стоимость полученной правильной скобочной последовательности?
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных записано одно целое число $$$k$$$ ($$$0 \le k \le 5$$$) — наибольшее количество действий, которые вы можете совершить.
Во второй строке записана непустая скобочная последовательность, она состоит только из символов '(' и ')'.
Суммарная длина скобочных последовательностей по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
На каждый набор входных данных выведите одно целое число — наименьшая стоимость правильной скобочной последовательности после того, как вы проделаете над ней не более $$$k$$$ действий.
70()0(())1(())5()1(()()(()))2((())()(()())((())))3((())()(()())((())))
0 1 0 0 1 4 2
