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

Дана строка $$$s$$$ четной длины, состоящая из символов «(», «)», «[» и «]», то есть из скобок двух типов (круглых и квадратных).

Назовем строку $$$t$$$ красивой, если для нее выполняются одновременно два условия:

  • подпоследовательность из всех круглых скобок образует правильную скобочную последовательность$$$^{\text{∗}}$$$;
  • подпоследовательность из всех квадратных скобок образует правильную скобочную последовательность.

Например, строка «[(][)[]]()» красивая, так как подпоследовательность всех круглых скобок в ней «()()» образует правильную скобочную последовательность и подпоследовательность всех квадратных в ней «[][[]]» образует правильную скобочную последовательность.

Вы бы хотели превратить $$$s$$$ в любую красивую строку, для этого вы можете изменять символы: за одно действие вы можете выбрать позицию $$$i$$$, такую что $$$1 \le i \le n$$$ и изменить символ $$$s_{i}$$$ на любую круглую или квадратную скобку.

Какое минимальное количество действий необходимо совершить, чтобы получить из $$$s$$$ любую красивую строку?

$$$^{\text{∗}}$$$Скобочная последовательность называется правильной, если путем вставки в неё символов «+» и «1» можно получить из неё корректное математическое выражение. Например, последовательности «(())()», «[]» и «(()(()))» — правильные, в то время как «)(», «[[]» и «(()))(» — нет.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — длина строки $$$s$$$. Гарантируется, что $$$n$$$ четное.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую только из символов «(», «)», «[» и «]».

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

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

Для каждого набора входных данных выведите одно целое число — ответ на задачу.

Пример
Входные данные
5
2
[)
4
[)[(
4
))[[
4
([)]
6
[)]](]
Выходные данные
1
2
2
0
2
Примечание

В первом наборе входных данных из $$$s$$$ можно получить «[]», изменив второй символ.

Во втором наборе входных данных из $$$s$$$ за $$$2$$$ действия можно получить «[][]», изменив символы в позициях $$$2$$$ и $$$4$$$.

В третьем наборе входных данных из $$$s$$$ за $$$2$$$ действия можно получить «()[]», изменив символы в позициях $$$1$$$ и $$$4$$$.

В четвертом наборе входных данных $$$s$$$ уже красивая, так как её можно разделить на подпоследовательность «()» и «[]».