CF1593G.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 \lt 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 \gt 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.

给定一个由圆括号和方括号组成的序列。你可以通过执行以下操作来修改该序列：

1. 改变某个括号的朝向（即由左括号变为右括号，或由右括号变为左括号），但不改变其形状：即可以将 '(' 变为 ')'，或将 ')' 变为 '('；可以将 '[' 变为 ']'，或将 ']' 变为 '['。该操作花费 $0$ 卢布。
2. 将任意一个方括号替换为具有相同朝向的圆括号：即可以将 '[' 变为 '('，但不能将 '(' 变为 '['；同理，可以将 ']' 变为 ')'，但不能将 ')' 变为 ']'。该操作花费 $1$ 卢布。

上述操作可按任意顺序执行任意多次。

给定一个长度为 $n$ 的字符串 $s$，以及 $q$ 个形如 "l r" 的查询，其中 $1 \le l \lt 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"（即两序列的拼接）也是合法括号序列。

例如，""、"(()[])、"[()()]()" 和 "(())()" 是合法括号序列，而 "("、"[([)]" 和 ")))" 不是。

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 \lt 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$.

第一行包含一个整数 $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 \lt r \le n$，其中 $n$ 是字符串 $s$ 的长度）。保证子串 $s[l \dots r]$ 的长度为偶数。

保证所有测试用例中给出的字符串总长度不超过 $10^6$。所有测试用例中给出的 $q$ 值之和不超过 $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.

对于每个测试用例，对每个查询，在单独的一行中输出一个整数 $x$（$x \ge 0$）—— 使给定子字符串成为合法括号序列所需支付的最小代价。

Consider the first test case. The first query describes the whole given string, the string can be turned into the following correct bracket sequence: "([()])()[[]]". The forms of the brackets aren't changed so the cost of changing is $0$.

The second query describes the substring ")[)()]". It may be turned into "(()())", the cost is equal to $2$.

The third query describes the substring "))[)". It may be turned into "()()", the cost is equal to $1$.

The substrings of the second test case contain only round brackets. It's possible to prove that any sequence of round brackets having an even length may be turned into a correct bracket sequence for the cost of $0$ burles.

In the third test case, the single query describes the string "[]" that is already a correct bracket sequence.

考虑第一个测试用例。第一个查询描述了整个给定字符串，该字符串可以转化为如下合法括号序列：“([()])()[[]]”。括号的类型未发生改变，因此修改代价为 $0$。

第二个查询描述了子串 “)[)()]”。它可以被转化为 “(()())”，代价为 $2$。

第三个查询描述了子串 “))[)”。它可以被转化为 “()()”，代价为 $1$。

第二个测试用例中的所有子串仅包含圆括号。可以证明：任意长度为偶数的圆括号序列均可在 $0$ burles 的代价下转化为合法括号序列。

在第三个测试用例中，唯一的查询描述的字符串为 “[]”，它本身已是合法括号序列。