U652246 [YCU Cup] 威汉森的石山代码

**Aerhuo** 最近在组织大家进行寒假集训，要求每人每天刷 5 道题。 然而，大一的 **威汉森**（绿名）却总是摸鱼。他声称自己 2 小时写出的代码是“经过深思熟虑的架构设计”，但 **烤小鱼**（队长）看了一眼后惊呼：“这简直就是石山代码！全是嵌套的 `if` 和递归！” 威汉森不服气，还要拉着 **HM** 进行 PK。为了防止威汉森那层层嵌套的递归函数导致评测机爆栈，Aerhuo 决定先写一个程序，检测一下威汉森代码的**最大递归深度**。

我们将威汉森代码中的一次函数递归调用记作一个左括号 `(`，函数返回记作一个右括号 `)`。 给出一个字符串 $S$，表示威汉森代码的调用执行序列。题目保证 $S$ 是一个**合法的括号序列**（即每一次调用都有对应的返回，且结构正确）。 请你计算这段代码在运行过程中，**调用栈的最大深度**是多少？ **本题包含多组测试数据。**

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试数据的组数。 接下来对于每组测试数据： - 第一行包含一个整数 $n$，表示字符串 $S$ 的长度。 - 第二行包含一个字符串 $S$，保证只包含 `(` 和 `)`，且合法。

对于每组测试数据，输出一行一个整数，表示该组数据的最大递归深度。

**威汉森**：“你看，我这代码虽然缩进有点多，但逻辑是完美的！” **烤小鱼**：“你这缩进都快跑到屏幕外面去了……” ## 数据范围 对于 $100\%$ 的数据， $1 \le T \le 100$， $2 \le n \le 10^5$，且单测试点数据的 $n$ 之和 $\sum n \le 2 \cdot 10^5$。 保证 $S$ 是合法的括号序列。