Monocarp 有一个规则的括号序列 $$$s$$$,长度为 $$$n$$$($$$n$$$ 是偶数)。他甚至想出了自己的方法来计算其成本。
他知道在常规括号序列(RBS)中,每个左括号与相应的右括号配对。因此,他决定将 RBS 的成本计算为相应括号对之间的距离之和。
例如,让我们看一下 RBS (())()。它有三对括号:
- (__)__: $$$1$$$ 位置和 $$$4$$$ 位置括号之间的距离为 $$$4 - 1 = 3$$$;
- _()___: 距离为 $$$3 - 2 = 1$$$;
- ____():距离为 $$$6 - 5 = 1$$$。
不幸的是,由于数据损坏,Monocarp 丢失了奇数位置 $$$s_1、s_3、\dots、s_{n-1}$$$ 上的所有字符。仅保留偶数位置上的字符 ($$$s_2, s_4, \dots, s_{n}$$$)。例如,(())() 变成了_(_)_)。
Monocarp 希望通过在奇数位置上放置括号来恢复他的 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$$$ 获得常规括号序列的最小成本。
示例
输入 #1
4 6 _(_)_) 2 _) 8 _)_)_)_) 8 _(_)_(_)
输出 #1
5 1 4 8
注意
在第一个测试用例中,最好使 $$$s$$$ 等于 (())()。 $$$s$$$ 的成本将等于 $$$3 + 1 + 1 = 5$$$。
在第二个测试用例中,唯一的选择是使 $$$s$$$ 等于 (),成本为 $$$1$$$。
在第三个测试用例中,唯一可能的 RBS 是 ()()()(),成本为 $$$1 + 1 + 1 + 1 = 4$$$。
在第四个测试用例中,最佳方案是使 $$$s$$$ 等于 (())(()),成本为 $$$3 + 1 + 3 + 1 = 8$$$。