题目描述

给定一个字符串 $s$，由两种括号组成：'(', ')', '[' 和 ']'。

一个字符串被称为正规括号序列（RBS），如果它属于以下类型之一：

• 空字符串；
• '(' + RBS + ')'；
• '[' + RBS + ']'；
• RBS + RBS。

其中加号表示两个字符串的连接。

每次操作，你可以选择字符串 $s$ 的一个非空子序列（不一定连续），该子序列是一个 RBS，将其从字符串中移除，并将剩余部分按原顺序连接。

你最多可以进行多少次这样的操作？

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

接下来的 $t$ 行中，每行包含一个非空字符串，仅由字符 '(', ')', '[' 和 ']' 组成。所有测试用例的字符串总长度不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示你最多可以对给定字符串 $s$ 执行的操作次数。

说明/提示

在第一个样例中，你可以直接删除整个字符串。

在第二个样例中，你可以先删除第 $1$ 和 $2$ 个括号：“[]()”，剩下“()”。之后你可以将其全部删除。你也可以一开始就删除整个字符串，但那样只能得到一次操作，而不是两次。

在第三个样例中，你可以先删除第 $1$ 和 $3$ 个括号：“([)]”，它们组成一个 RBS “()”。然后剩下“[]”，你可以将其全部删除。

在第四个样例中，没有任何子序列是 RBS，因此你无法进行任何操作。

在第五个样例中，你可以删除第 $2$ 和 $4$ 个括号：“)[(]”，得到“)(”。你无法再从中删除任何内容。

由 ChatGPT 4.1 翻译

样例

5
()
[]()
([)]
)]([
)[(]

1
2
2
0
1