给定一个字符串 $$$s$$$,由两种类型的括号组成:'(', ')', '[' 和 ']'。
如果字符串属于以下类型之一,则称为常规括号序列 (RBS):
- 空字符串;
- '(' + RBS + ')';
- '[' + RBS + ']';
- 苏格兰皇家银行 + 苏格兰皇家银行。
其中 plus 是两个字符串的串联。
在一步操作中,您可以选择字符串 $$$s$$$ 的非空子序列(不一定是连续的),该子序列是 RBS,将其从字符串中删除并连接其余部分而不更改顺序。
您最多可以执行多少步?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
接下来的 $$$t$$$ 行均包含一个非空字符串,仅由字符“(”、“)”、“[”和“]”组成。所有测试用例的字符串总长度不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您可以对给定字符串 $$$s$$$ 执行的最大移动次数。
示例
输入 #1
5 () []() ([)] )]([ )[(]
输出 #1
1 2 2 0 1
注意
在第一个示例中,您可以删除整个字符串。
在第二个示例中,您可以先删除 $$$1$$$ 和 $$$2$$$ 位置上的括号:“[]()”,然后留下“()”。之后您可以将其全部删除。你可以从一开始就擦除整个字符串,但你会得到一步而不是两步。
在第三个示例中,您可以先擦除 $$$1$$$ 和 $$$3$$$ 位置上的括号:“([)]”。它们组成了RBS“()”。然后留下“[]”,这样你就可以把它整个删除了。
在第四个示例中,没有 RBS 子序列,因此您根本无法执行移动。
在第五个示例中,您可以删除位置 $$$2$$$ 和 $$$4$$$ 上的括号:“)[(]”并得到“)(”作为结果。您不能从中删除任何内容。