CF1452C.Two Brackets

You are given a string $s$, consisting of brackets of two types: '(', ')', '[' and ']'.

A string is called a regular bracket sequence (RBS) if it's of one of the following types:

• empty string;
• '(' + RBS + ')';
• '[' + RBS + ']';
• RBS + RBS.

where plus is a concatenation of two strings.

In one move you can choose a non-empty subsequence of the string $s$ (not necessarily consecutive) that is an RBS, remove it from the string and concatenate the remaining parts without changing the order.

What is the maximum number of moves you can perform?

给你一个字符串 $s$，其中只包含两种类型的括号：'('、')'、'[' 和 ']'。

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

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

其中，“+” 表示两个字符串的连接。

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

你最多能执行多少次这样的操作？

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Each of the next $t$ lines contains a non-empty string, consisting only of characters '(', ')', '[' and ']'. The total length of the strings over all testcases doesn't exceed $2 \cdot 10^5$.

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

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

For each testcase print a single integer — the maximum number of moves you can perform on a given string $s$.

对于每个测试用例，输出一个整数——即在给定字符串 $s$ 上所能执行的最大操作次数。

In the first example you can just erase the whole string.

In the second example you can first erase the brackets on positions $1$ and $2$: "[]()", then "()" is left. After that you can erase it whole. You could erase the whole string from the beginning but you would get one move instead of two.

In the third example you can first erase the brackets on positions $1$ and $3$: "([)]". They form an RBS "()". Then "[]" is left, so you can erase it whole.

In the fourth example there is no subsequence that is an RBS, so you can't perform a move at all.

In the fifth example you can erase the brackets on positions $2$ and $4$: ")[(]" and get ")(" as a result. You can erase nothing from it.

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

在第二个例子中，你可以先删除位置 $1$ 和 $2$ 上的括号：“[]()”，之后剩下 “()”。接着你可以将它整体删除。你也可以从一开始就把整个字符串删除，但那样只会用 1 步，而不是 2 步。

在第三个例子中，你可以先删除位置 $1$ 和 $3$ 上的括号：“([)]”。它们构成一个正则括号序列（RBS）“()”。之后剩下 “[]”，因此你可以将其整体删除。

在第四个例子中，不存在任何作为正则括号序列（RBS）的子序列，因此根本无法执行任何操作。

在第五个例子中，你可以删除位置 $2$ 和 $4$ 上的括号：“)[(]”，结果得到 “)(”。你无法从中删除任何内容。