如果一个括号表达式里每一个左(右)括号都能和一个右(左)括号匹配,那么就称这个括号表达式合法。
比如 ()()() 、(()()) 、(((()))) 就是合法的括号表达式, ()()( 、)()( 、(())(() 就不是合法的括号表达式。
现在,luo 有一个包含 ? 的括号表达式, 其中 ? 可以被替代为 ( 或者 )(必须替代,且替代完后位置不发生改变)。luo 想知道是否可以知道一种替代方案,使得这个括号表达式合法。如果有,则输出 YES,反之,则输出 NO。
输入
输入第一行包括一个整数 t，表示一共有 t 组测试样例。
接下来 t 行,每行为一个仅由 ( 、 ) 、? 组成的字符串,第 i 行表示第 i 组测试样例
1 \leq t \leq 1000
每个字符串的长度不超过 150
输出
输出共 t 行,第 i 行为第 i 组测试样例的结果
样例
| 标准输入 复制文本 |
6 (?) (??) (?)( ()()?? (?)(?) ()?() |
| 标准输出 复制文本 |
NO YES NO YES YES NO |