#P18083. Palindromic and Balanced
Palindromic and Balanced
Palindromic and Balanced
题目描述
括号串仅含 (、)。回文串指从左到右和从右到左读完全相同的串;空串也算回文串。
平衡括号串定义如下:空串是平衡括号串;若 平衡,则 平衡;若 均平衡,则它们的拼接 平衡。
称括号串 为回文平衡括号串,当且仅当它是平衡括号串,且去掉第一个和最后一个字符后的串 是回文串。特别地,空串和 () 也满足定义。
给定长度为 的括号串 ,求其最长的回文平衡括号子序列的长度。子序列通过删除任意个字符得到,剩余字符的相对顺序保持不变;可以删除全部字符。
输入格式
第一行一个整数 ,表示测试组数。每组数据包含两行:第一行一个整数 ;第二行一个长度为 的括号串 。
,;所有组的 之和不超过 。
输出格式
每组输出一行一个整数,表示最长合法子序列的长度。
样例输入
3
5
(()((
7
)))((((
8
())(()()
样例输出
2
0
6