Sharmeen the little girl learned about parentheses a few days ago. So as usual Mozahid gives her a problem to solve related to parentheses. As she is a little girl, she can’t find a solution. As you are a good programmer can you solve it for Sharmeen?

You will be given a string consisting of only parentheses ‘(‘ or ‘)’ and question marks ‘?’. You can replace a question mark with an opening or closing parenthesis. If it is possible to make the string a valid parentheses sequence, output yes otherwise no. You have to replace all the question marks with parentheses.

Input

First line of the input is the number of test cases T (1 <= T <= 10^5).

A string of length n (1 <= n <= 10^5) consisting of only ‘(‘ , ‘)‘ or ‘?’.

Total length of all string will be at most 10^6.

Output

For each testcase, if it is possible to make the string a valid parentheses sequence replacing the ‘?’ marks with parentheses output ‘yes’ otherwise ‘no’ without quotes in one line.

Constraints

1 <= T <= 10^5

1 <= n <= 10^5

Total length of all strings will be at most 10^6.

See the sample input output for better understanding.

Example

Input:
2
(()??((??)
((??

Output:
yes
yes

Explanation:

Possible valid parentheses sequences for test case 1 are:-