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

Задана последовательность из круглых и квадратных скобок. Над этой последовательностью можно произвести следующие операции:

  1. поменять вид скобки с открывающей на закрывающую и наоборот, не меняя форму скобки: то есть можно поменять '(' на ')' и ')' на '('; можно поменять '[' на ']' и ']' на '['. Эта операция стоит $$$0$$$ бурлей.
  2. взять любую квадратную скобку и поменять на круглую, не меняя направление скобки: то есть можно поменять '[' на '(', но не '(' на '['; можно поменять ']' на ')', но не ')' на ']'. Эта операция стоит $$$1$$$ бурль.

Операции можно производить в любом количестве в любом порядке.

Задана строка $$$s$$$ длины $$$n$$$ и $$$q$$$ запросов вида «l r», где $$$1 \le l < r \le n$$$. Для каждой подстроки $$$s[l \dots r]$$$ найдите минимальную цену, которую нужно заплатить, чтобы сделать её правильной скобочной последовательностью. Гарантируется, что подстрока $$$s[l \dots r]$$$ имеет чётную длину.

Запросы надо обрабатывать независимо, то есть изменения в строке, сделанные для ответа на запрос $$$i$$$, не влияют на запросы $$$j$$$ ($$$j > i$$$). Иными словами, при обработке запроса подстрока $$$s[l \dots r]$$$ берётся из первоначальной заданной строки $$$s$$$.

Правильная скобочная последовательность — это последовательность, которую можно построить по следующим правилам:

  • пустая последовательность является правильной скобочной;
  • если «s» — правильная скобочная последовательность, то последовательности «(s)» и «[s]» являются правильными скобочными;
  • если «s» и «t» – правильные скобочные последовательности, то последовательность «st» (соединение этих последовательностей) является правильной скобочной.

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

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

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

Первая строка каждого набора данных содержит непустую строку $$$s$$$, содержащую только круглые ('(' и ')') и квадратные ('[' и ']') скобки. Длина строки не превышает $$$10^6$$$. Строка содержит не менее $$$2$$$ символов.

Вторая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Далее идут $$$q$$$ строк, содержащих два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$, где $$$n$$$ — длина строки $$$s$$$). Гарантируется, что подстрока $$$s[l \dots r]$$$ имеет чётную длину.

Гарантируется, что сумма длин всех строк, заданных во всех наборах входных данных, не превышает $$$10^6$$$. Сумма всех $$$q$$$, заданных во всех наборах входных данных, не превышает $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите в отдельной строке целое число $$$x$$$ ($$$x \ge 0$$$) — минимальную цену, которую нужно заплатить, чтобы данная подстрока стала правильной скобочной последовательностью.

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

Рассмотрим первый набор входных данных. Первый запрос описывает всю строку, её можно привести к следующей правильной скобочной последовательности: «([()])()[[]]». Форма скобок не изменена, поэтому стоимость изменения равна $$$0$$$.

Второй запрос описывает подстроку «)[)()]». Её можно привести к последовательности «(()())», стоимость равна $$$2$$$.

Третий запрос описывает подстроку «))[)». Её можно привести к последовательности «()()», стоимость равна $$$1$$$.

Во втором наборе входных данных все подстроки состоят только из круглых скобок. Можно показать, что любую последовательность чётной длины из круглых скобок можно привести к правильной за $$$0$$$ бурлей.

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