如果可以通过在序列中插入字符 + 和 1 来获得正确的算术表达式,则该括号序列称为正则序列。例如,序列 (())()、() 和 (()(())) 是规则的,而 )(、(() 和 (()))( 则不是。我们将规则的括号序列称为“RBS”。
给定一个由 $$$n$$$ 个字符 (, ) 和/或 ? 组成的序列 $$$s$$$。此序列中恰好有一个字符(并且恰好有一个字符)。
你必须替换每个字符?与 ) 或 ( (不同的字符 ? 可以用不同的括号替换)。您不能对字符重新排序、删除它们、插入其他字符,并且每个 ? 都必须被替换。
确定在这些替换后是否可以获得 RBS。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由一行包含 $$$s$$$ ($$$2 \le |s| \le 100$$$) — 一系列字符 (, ) 和/或 ? 组成。此序列中恰好有一个字符(并且恰好有一个字符)。
输出
对于每个测试用例,如果可以获得常规括号序列,则打印 YES,否则打印 NO}。
您可以在任何情况下打印每个字母(例如,YES,Yes,yes,yE 都将被识别为肯定答案)。
示例
输入 #1
5 () (?) (??) ??() )?(?
输出 #1
YES NO YES YES NO
注意
在第一个测试用例中,序列已经是 RBS。
在第三个测试用例中,您可以通过以下方式获取 RBS:()() 或 (())。
在第四个测试用例中,您可以获得RBS,如下所示:()()。