给出了一系列圆括号和方括号。您可以通过以下操作更改顺序:
1. 在不改变括号形式的情况下,将括号的方向从左括号改为右括号,反之亦然:即可以将 '(' 更改为 ')',')' 更改为 '(';可以将 '[' 更改为 ']',']' 更改为 '['。该操作需要花费 $$$0$$$ burles。
2. 将任何方括号更改为具有相同方向的圆括号:即,您可以将 '[' 更改为 '(',但不能将 '(' 更改为 '[';同样,您可以将 ']' 更改为 ')',但不能将 ')' 更改为 ']'。手术费用为$$$1$$$ burle。
这些操作可以按任意顺序执行任意次数。
给您一个长度为 $$$n$$$ 的字符串 $$$s$$$ 和类型为“l r”的 $$$q$$$ 查询,其中 $$$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$$$) — 使给定子字符串成为正确的括号序列所需的最小成本。
示例
输入 #1
3 ([))[)()][]] 3 1 12 4 9 3 6 )))))) 2 2 3 1 4 [] 1 1 2
输出 #1
0 2 1 0 0 0
注意
考虑第一个测试用例。第一个查询描述了整个给定字符串,该字符串可以转换为以下正确的括号序列:“([()])()[[]]”。括号的形式没有改变,所以改变的成本是$$$0$$$。
第二个查询描述子字符串“)[)()]”。可能会变成“(()())”,成本等于$$$2$$$。
第三个查询描述子字符串“))[)”。可能会变成“()()”,成本等于$$$1$$$。
第二个测试用例的子字符串仅包含圆括号。可以证明,任何具有偶数长度的圆括号序列都可以以 $$$0$$$ burles 的成本转换为正确的括号序列。
在第三个测试用例中,单个查询描述的字符串“[]”已经是正确的括号序列。