MOZSAPAR - Sharmeen and parentheses

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:-

  • (())((()))
  • (()()(()))

  • Added by:Mozahid
    Date:2019-09-14
    Time limit:1s
    Source limit:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Languages:All

    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.