C. Две скобки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность $$$s$$$, состоящая из скобок двух типов: '(', ')', '[' и ']'.

Строка называется правильной скобочной последовательностью (ПСП), если она одного из следующих типов:

  • пустая строка;
  • '(' + ПСП + ')';
  • '[' + ПСП + ']';
  • ПСП + ПСП.

где плюс — это операция склеивания двух строк.

За один ход можно выбрать непустую подпоследовательность символов строки $$$s$$$ (не обязательно подряд идущих), которые являются ПСП, удалить их из строки и склеить оставшиеся части, не изменяя порядка.

Какое наибольшее количество ходов можно совершить?

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

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

В каждой из следующих $$$t$$$ строк содержится одна непустая строка, состоящая только из символов '(', ')', '[' и ']'. Суммарная длина строк по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

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

В первом примере можно просто удалить всю строку.

Во втором примере можно сначала удалить скобки на позициях $$$1$$$ и $$$2$$$: «[]()», затем останется «()». Потом можно удалить строку целиком. Можно было и сразу удалить всю строку, но тогда была бы одна операция вместо двух.

В третьем примере можно сначала удалить скобки на позициях $$$1$$$ и $$$3$$$: «([)]». Они образуют ПСП «()». Затем останется «[]», поэтому можно удалить ее целиком.

В четвертом примере нет ни одной подпоследовательности, которая является ПСП, поэтому нельзя совершить ни один ход.

В пятом примере можно удалить скобки на позициях $$$2$$$ и $$$4$$$: «)[(]» и получить «)(» в результате. Из нее ничего нельзя удалить.