Yousef 给了你一个长度为 ~n~ 的序列 ~s~，该序列仅由字符 '~\texttt{(}~' 和 '~\texttt{)}~' 组成。你被允许至多一次执行以下操作：

• 选择 ~s~ 的一个子串~^{*}~ 并将其移除。然后，你可以将移除的字符逐个重新插入剩余的字符串中。每个字符可以独立于其他字符放置在任意位置。

Yousef 想要你判断在执行至多一次操作后，是否有可能得到一个正则括号序列~^{\dagger}~。

~^{*}~ 子串是字符串的连续子段。例如，"acab" 是 "abacaba" 的子串（它从位置 3 开始，到位置 6 结束），但 "aa" 或 "d" 不是该字符串的子串。因此，字符串 ~s~ 从位置 ~l~ 到位置 ~r~ 的子串为 ~s[l, r] = s_l s_{l+1} \dots s_r~。

~^{\dagger}~ 正则括号序列是一种括号序列，可以通过在序列的原始字符之间插入字符 1 和 + 将其转换为正确的算术表达式。例如：

• 括号序列 ~()()~ 和 ~(())~ 是正则的（所得表达式为：~(1)+(1)~ 和 ~((1+1)+1)~）；
• 括号序列 ~)(~、 ~(~ 和 ~)~ 不是正则的。

输入

第一行包含一个整数 ~t~（~1 \le t \le 10^4~）—— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 ~n~（~1 \le n \le 2 \cdot 10^5~）—— 字符串 ~s~ 的长度。

每个测试用例的第二行包含一个长度为 ~n~ 的序列 ~s~，仅由字符 '~\texttt{(}~' 和 '~\texttt{)}~' 组成。

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

输出

对于每个测试用例，如果该序列可以变为正则，则输出 "YES"，否则输出 "NO"。

你可以以任意大小写输出答案。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 都将被视为肯定回答。

样例

输入

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{)(}~，将其移除，然后按如下方式重新插入字符：

$$\displaystyle \texttt{()}{\color{red}{\texttt{)(}}}\texttt{()} \to \texttt{()()} \to {\color{green}{\texttt{(}}}\texttt{()()}{\color{green}{\texttt{)}}} $$

因此我们得到了一个正则括号序列，答案是 "YES"。