题目描述

Saki 在 Koboshi 的安利下开始玩起了一款简单的游戏。

游戏中，每个关卡会给你一个合法的括号串。合法的括号串定义如下：

• 空串和 () 为合法的括号串；
• 设 A 为合法的括号串，那么 (A) 为合法的括号串；
• 设 A 和 B 为合法的括号串，那么 AB 为合法的括号串。

游戏中，每次操作可以交换两个相邻的括号，而游戏的目标是通过若干次操作使括号串变得非法。

而 Saki 并不知道自己的操作数是否已经优化到最少，所以她想问游戏领域大神 Koboshi 她的操作数是否是最少的。而 Koboshi 因为手和脚都在玩游戏，所以她把这件事情丢给了你，让你求得通关所需最少的操作次数。

当然游戏有 $T$ 个关卡，Saki 需要知道每一关通关所需的最少操作次数。

输入格式

第一行一个正整数 $T$，代表关卡数量。

接下来 $T$ 行，每行一个合法的括号串，表示每一关给出的括号串。

输出格式

共 $T$ 行，第 $i$ 行表示通过第 $i$ 关所需要的最少的操作次数。

3
()
(())
(()()())

1
2
2

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 100$，$2 \le n \le 8$；
• 对于另外 $30\%$ 的数据，$1 \le T \le 50$，$2 \le n, \sum n \le 100$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$2 \le n, \sum n \le 10^6$。保证 $S$ 是合法的括号序列。