#P18083. Palindromic and Balanced

Palindromic and Balanced

Palindromic and Balanced

题目描述

括号串仅含 (、)。回文串指从左到右和从右到左读完全相同的串;空串也算回文串。

平衡括号串定义如下:空串是平衡括号串;若 ss 平衡,则 (s)(s) 平衡;若 s,ts,t 均平衡,则它们的拼接 stst 平衡。

称括号串 s=s1⋯sks=s_1\cdots s_k 为回文平衡括号串,当且仅当它是平衡括号串,且去掉第一个和最后一个字符后的串 s2⋯sk−1s_2\cdots s_{k-1} 是回文串。特别地,空串和 () 也满足定义。

给定长度为 nn 的括号串 ss,求其最长的回文平衡括号子序列的长度。子序列通过删除任意个字符得到,剩余字符的相对顺序保持不变;可以删除全部字符。

输入格式

第一行一个整数 tt,表示测试组数。每组数据包含两行:第一行一个整数 nn;第二行一个长度为 nn 的括号串 ss。

1≤t≤50001\le t\le5000,1≤n≤50001\le n\le5000;所有组的 nn 之和不超过 10410^4。

输出格式

每组输出一行一个整数,表示最长合法子序列的长度。

样例输入

3
5
(()((
7
)))((((
8
())(()()

样例输出

2
0
6