该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

江月诗正在为派对设计一个由括号组成的装饰图案。这个图案用长度为 $n$ 的字符串 $s$ 表示，其中仅包含左括号 ( 和右括号 )。

江月诗可以至多执行一次以下操作：选择 $s$ 的一个子串并将其删除，再把删除的所有字符逐个插回剩余字符串。每个字符的插入位置可以任意选择，彼此独立。

请判断经过这样的调整，能否得到一个合法括号序列。

子串是字符串中连续的一段字符。合法括号序列要求所有括号能够正确匹配；等价地，左右括号总数相等，且任意前缀中左括号的数量都不少于右括号的数量。例如，()、()()、(()) 合法，)(、(、) 不合法。

输入格式

第一行包含一个整数 $t$，表示测试用例数量，满足 $1\le t\le10^4$。

每组测试用例包含两行：第一行为整数 $n$，满足 $1\le n\le2\times10^5$；第二行为长度恰好为 $n$ 的括号字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2\times10^5$。

输出格式

对每组测试用例，能够通过至多一次操作得到合法括号序列则输出 YES，否则输出 NO。

输入输出样例 1

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

YES
YES
NO
YES
NO
NO

提示/说明

第一组测试用例中的 () 已经合法，无需操作。

第二组测试用例可以删除第 $2$ 个字符 (，再将它插入开头，得到 ()。

第三组测试用例无法得到合法括号序列。

第四组测试用例可以删除第 $3$ 至第 $4$ 个字符组成的子串 )(，剩下 ()()，再把 ( 插到开头、) 插到末尾，得到 (()())。