题目描述

Kevin 有一个长度为 (n) 的括号序列 (s)，只包含左括号 ( 和右括号 )。
他最多可以执行一次如下操作：

1. 选择 (s) 的一个 子串（连续的一段），将其删除。
2. 然后，将删除的这些括号逐个重新插入到剩余的字符串中。每个括号可以放在任意位置，与其他括号无关。

Kevin 想知道：是否有可能在执行最多一次操作后，整个序列变成一个 合法括号序列。

合法括号序列满足：

• 左括号和右括号数量相等；
• 在任意前缀中，左括号的数量不少于右括号的数量。

输入格式

第一行一个整数 t（1 <= t <= 10000），表示测试用例的数量。 （保证t组样例n的和小于等于200000） 每个测试用例由两行组成：

• 第一行一个整数 n（1 <= n <= 200000），表示字符串 s 的长度。
• 第二行一个长度为 n 的字符串 s，仅包含 ( 和 )。

保证所有测试用例的 n 之和不超过 200000。

输出格式

对于每个测试用例，如果 Kevin 能达到目标，输出 "Yes"，否则输出 "No"。

样例

6
2
()
2
)(
3
(((
6
())(()
4
(()(
5
)()()

Yes
Yes
No
Yes
No
No

样例解释

在第一个测试案例中，字符串 $s$ 已经是一个合法括号序列，因此答案是 "Yes"。

在第二个测试案例中，我们可以删除子串 $s[2, 2] = \texttt{(}$ 并将其重新插入字符串的开头，使其成为 $s = \texttt{()}$ ，因此答案为 "Yes"。

在第三个测试案例中，我们无法进行操作并得到合法括号序列，因此答案为 "No"。

在第四个测试案例中，我们可以选择子串 $s[3, 4] = \texttt{)(}$ ，删除它，然后重新插入字符，答案是 "Yes"。