题目描述

Monocarp 有一个长度为 $n$ 的正规括号序列 $s$（$n$ 是偶数）。他甚至想出了自己计算其代价的方法。

他知道，在一个正规括号序列（RBS）中，每一个左括号都与对应的右括号配对。因此，他决定将 RBS 的代价定义为所有配对括号之间距离的总和。

例如，考虑 RBS (())()。它有三个括号对：

• (__)__：第 $1$ 位和第 $4$ 位括号之间的距离为 $4 - 1 = 3$；
• _()___：第 $2$ 位和第 $3$ 位括号之间的距离为 $3 - 2 = 1$；
• ____()：第 $5$ 位和第 $6$ 位括号之间的距离为 $6 - 5 = 1$。

所以 (())() 的代价为 $3 + 1 + 1 = 5$。不幸的是，由于数据损坏，Monocarp 丢失了所有奇数位置上的字符 $s_1, s_3, \dots, s_{n-1}$。只剩下偶数位置上的字符（$s_2, s_4, \dots, s_n$）。例如，(())() 变成了 _(_)_)。

Monocarp 想通过在奇数位置放置括号来恢复他的 RBS。但由于恢复后的 RBS 可能不唯一，他想选择代价最小的那一个。对于 Monocarp 来说这太难了，所以你能帮帮他吗？

提示：正规括号序列是只包含括号的字符串，使得该序列在插入 1-s 和 +-s 后，能构成一个合法的数学表达式。例如，()、(()) 或 (()())() 是 RBS，而 )、()( 或 ())(()) 不是。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 5000$）——表示测试用例的数量。接下来是 $t$ 组测试数据。

每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$，$n$ 为偶数）——字符串 $s$ 的长度。

每组测试数据的第二行包含一个长度为 $n$ 的字符串 $s$，所有奇数位置上的字符都是 '_'，所有偶数位置上的字符都是 '(' 或 ')'。

附加约束：

• $s$ 至少可以恢复成一个正规括号序列；
• 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数——将 $s$ 中的 '_' 替换为括号后，能得到的正规括号序列的最小代价。

说明/提示

在第一个测试用例中，最优做法是将 $s$ 变为 (())()，其代价为 $3 + 1 + 1 = 5$。

在第二个测试用例中，唯一的选择是 ()，代价为 $1$。

在第三个测试用例中，唯一可能的 RBS 是 ()()()()，代价为 $1 + 1 + 1 + 1 = 4$。

在第四个测试用例中，最优做法是将 $s$ 变为 (())(())，代价为 $3 + 1 + 3 + 1 = 8$。

由 ChatGPT 4.1 翻译

样例

4
6
_(_)_)
2
_)
8
_)_)_)_)
8
_(_)_(_)

5
1
4
8