Valid Strings
Arnab loves brackets and any valid sequence of brackets. On his birthday, he expected a valid sequence of brackets from his friends. He is upset because some of his friends deliberately gifted him an invalid sequence. Now, Arnab decided to fix the sequence himself by moving only one of the brackets in the sequence.
A bracket sequence ( S ) is valid only if: 1. S is empty 2. S is equal to “( t )”, where t is a valid sequence 3. S is equal to “( t1 t2 )” ie. concatenation of t1 and t2 , where t1 and t2 are valid sequences.
Arnab, being a lazy person wants you to check if the sequence can be made valid by moving just one bracket (if required).
Input format
First-line contains an integer TT where TT is the number of test cases. The next TT lines contain a String SS denoting the sequence.
Output format
For each test case on a new line, print Yes or No depending on whether it is possible or not to convert the string into a valid string.
Constraints:
1<=T<=701<=T<=70 1<=|S|<=1051<=|S|<=105 , where |S||S| denotes the length of the string.
Time Limit
11 second
Example
Input
1 )(
Output
Yes
Sample test case explanation
we have the sequence )( so by moving the first bracket to the last we get () so it becomes a valid string.