A14608 | Changing Brackets

A sequence of round and square brackets is given. You can change the sequence by performing the following operations:

1. change the direction of a bracket from opening to closing and vice versa without changing the form of the bracket: i.e. you can change '(' to ')' and ')' to '('; you can change '\[' to '\]' and '\]' to '\['. The operation costs $0$ burles.
2. change any square bracket to round bracket having the same direction: i.e. you can change '\[' to '(' but not from '(' to '\['; similarly, you can change '\]' to ')' but not from ')' to '\]'. The operation costs $1$ burle.

The operations can be performed in any order any number of times.

You are given a string $s$ of the length $n$ and $q$ queries of the type "l r" where $1 \le l < r \le n$ . For every substring $s[l \dots r]$ , find the minimum cost to pay to make it a correct bracket sequence. It is guaranteed that the substring $s[l \dots r]$ has an even length.

The queries must be processed independently, i.e. the changes made in the string for the answer to a question $i$ don't affect the queries $j$ ( $j > i$ ). In other words, for every query, the substring $s[l \dots r]$ is given from the initially given string $s$ .

A correct bracket sequence is a sequence that can be built according the following rules:

- an empty sequence is a correct bracket sequence;
- if "s" is a correct bracket sequence, the sequences "(s)" and "\[s\]" are correct bracket sequences.
- if "s" and "t" are correct bracket sequences, the sequence "st" (the concatenation of the sequences) is a correct bracket sequence.

E.g. the sequences "", "(()\[\])", "\[()()\]()" and "(())()" are correct bracket sequences whereas "(", "\[(\])" and ")))" are not.

The first line contains one integer $t$ ( $1 \le t \le 100$ ) — the number of test cases. Then $t$ test cases follow.

For each test case, the first line contains a non-empty string $s$ containing only round ('(', ')') and square ('\[', '\]') brackets. The length of the string doesn't exceed $10^6$ . The string contains at least $2$ characters.

The second line contains one integer $q$ ( $1 \le q \le 2 \cdot 10^5$ ) — the number of queries.

Then $q$ lines follow, each of them contains two integers $l$ and $r$ ( $1 \le l < r \le n$ where $n$ is the length of $s$ ). It is guaranteed that the substring $s[l \dots r]$ has even length.

It is guaranteed that the sum of the lengths of all strings given in all test cases doesn't exceed $10^6$ . The sum of all $q$ given in all test cases doesn't exceed $2 \cdot 10^5$ .

For each test case output in a separate line for each query one integer $x$ ( $x \ge 0$ ) — the minimum cost to pay to make the given substring a correct bracket sequence.