Wildcard Parentheses String

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string of '(', ')', '?', and '*', decide whether the '?' and '*' can be filled in to form a correct bracket string.

Level: Medium5 of 10
Topics: String, Greedy
Solved: No attempts yet

Problem

A string made of ( and ) is a correct bracket string under these rules.

If $S$ is the empty string, $S$ is a correct bracket string.
If $S$ is a correct bracket string, then ( $S$ ) is also a correct bracket string.
If $S$ and $T$ are correct bracket strings, then the concatenation $ST$ is also a correct bracket string.
A string that cannot be built with the three rules above is not a correct bracket string.

For example, (())() and ()() are correct bracket strings, while )( and ())( are not.

You are given a string $S$ made of (, ), ?, and *. Replace each ? with ( or ), and replace each * with a string of length 0 or more made of ( and ). Can $S$ become a correct bracket string?

Input

The first line contains the number of test cases $T$ . $(1 \le T \le 10\,000)$

Each test case is one line containing a string $S$ of length at least 1 and at most $500\,000$ . The total length of all strings does not exceed $500\,000$ .

Output

For each test case, print YES on its own line if $S$ can be turned into a correct bracket string by the replacements above. Otherwise, print NO.

Examples1

Example 1

Input

4
()??))
())*(())
*)))(((*
?()(?*))(()?

Expected output

YES
NO
YES
YES