2077 年,机器人决定一劳永逸地摆脱平衡括号序列!
括号序列称为 平衡 如果它可以通过以下形式语法构造。
- 空序列 $$$\varnothing$$$ 是平衡的。
- 如果括号序列 $$$A$$$ 是平衡的,则 $$$\mathtt{(}A\mathtt{)}$$$ 也是平衡的。
- 如果括号序列 $$$A$$$ 和 $$$B$$$ 是平衡的,则串联序列 $$$A B$$$ 也是平衡的。
你是对抗平衡括号序列的部门负责人,你的主要任务是确定哪些括号可以破坏,哪些不能破坏。
给你一个平衡的括号序列,由字符串 $$$s$$$ 表示,由字符组成 ( 和 )。由于机器人的能力不是无限的,它们可以移除 正是 一个开口支架和 正是 字符串中的一个右括号。
你的任务是确定机器人是否可以删除这样两个括号,从而使字符串 $$$s$$$ 不再是平衡的括号序列。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例都包含一个字符串 $$$s$$$ ($$$2 \leq |s| \leq 2 \cdot 10^5$$$) - 字符序列 ( 和 ).
保证$$$s$$$ 是一个平衡的括号序列。
还保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出“是“如果机器人可以使字符串不再是平衡的括号序列,并且”NO”否则。
您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“是", "是的", "是“,和”是”将被接受为肯定答案。
示例
输入复制
4(())(())()()()(())(())
输出复制
NO YES NO YES
注意
在第一个测试用例中,可以表明机器人将无法打破正确的括号序列。
在第二个测试用例中,删除括号的选项之一如下:
$$$\texttt{(())}\color{red}{\texttt{(}}\texttt{)(}\color{red}{\texttt{)}} \rightarrow \texttt{(()))(}$$$,这不是正确的括号序列。
在第四个测试用例中,删除的选项之一如下:
$$$\texttt{(}\color{red}{\texttt{(}}\texttt{))((}\color{red}{\texttt{)}}\texttt{)}\rightarrow \texttt{())(()}$$$,这不是正确的括号序列。