解题思路

给定只含 (、)、* 的字符串，题意要求：在某个连续子串中，把所有 * 全部忽略（删除）后，剩下的括号序列必须是有效括号串。于是可将问题转化为：

1. 先把整串中过滤出所有括号，得到只含 (、) 的序列 par，并记录这些括号在原串中的位置数组 pos。

2. 在 par 上求“最长有效括号”（经典 LVP）——可用 O(n) DP：

   • 设 dp[i] 表示以 i 位置结尾的最长有效括号长度（单位：括号个数），若 par[i] == ')' 且与其匹配的左括号在 j = i - 1 - dp[i-1] 且 par[j] == '('，则 dp[i] = dp[i-1] + 2 (+ dp[j-1] 若 j-1 >= 0).

题目内容

多多最近在处理一个字符串问题，该字符串由 '$($'、'$)$' 和 '$*$' 组成，多多希望找到最长的连续子串，使得当忽略所有 '$*$' 后，该子串是一个有效的括号子串。

有效括号子串需满足：

1. 括号成对闭合：每个 '$($' 都有一个对应的 '$)$'
2. 正确嵌套顺序：右括号不能出现在对应的左括号之前

输入描述

第一行输入为一个整数 $T$, 表示测试用例的组数 $(1 <= T <= 100)$

接下来 $T$ 组数据，每组测试用例包含两行:

第一行输入为一个整数 $N$ , 表示字符串的总长度 $(1 <= N <= 500,000)$

第二行输入为一个长度为 $N$ 字符串，字符串由 $($ 和 $)$ 以及 $*$ 组成

输出描述

输出包含 $T$ 行

每一输出为一个整数，满足要求的最长的连续子串的长度

补充说明

空字符串是有效括号子串

样例1

输入

3
8
*(*(**))
4
(()*
8
*(()(*)*

输出

8
3
6

样例2

输入

2
4
****
4
)))(

输出

4
0