Valid strings

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.


1<=T<=701<=T<=70 1<=|S|<=1051<=|S|<=105 , where |S||S| denotes the length of the string.

Time Limit

11 second



1 )(



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.

can the strings be already valid
will that be a yes