Cerință
Se dă un string $s$ ce conține “()” și cifre de la “0” la “9”. Din stringul $s$, se construiește stringul $t$ considerând fiecare caracter din $s$ în ordine și efectuând următoarele operații în funcție de caracterul curent:
- ”(” : se adaugă la final “(” la $t$.
- ”)”: se adaugă la final “)” la $t$.
- $0 \leq c \leq 9$: se șterg oricare $c$ caractere din $t$.
- Se garantează că operațiile se pot efectua mereu.
- Caracterele care trebuiesc șterse nu trebuie să fie consecutive.
Se poate construi $t$ astfel încât să fie corect parantezat?
Date de intrare
Prima linie conține un număr $t$ ($1 \leq t \leq 10^{4}$), reprezentând numărul de teste.
Pentru fiecare test, se dă un string $s$ ce conține paranteze și cifre (”()0123456789”).
Lungimea lui $s$ este cel mult $3 \cdot 10^{5}$ characters.
Se garantează ca lungimea totală a tuturor stringurilor nu depășește $3 \cdot 10^{5}$ characters.
Date de ieșire
Pentru fiecare test, se afișează Yes dacă este posibil să construiești pe $t$ astfel încât să fie corect parantezat, și No altfel.
Exemple
Input
2
((()(3)1
(()1)
Ieșire
Yes
No
Input
5
()1()
(())
()1((((2()())))3)()
((2))()
((1()))(1)()
Ieșire
No
Yes
Yes
No
Yes
Statement
You are given a string $s$ consisting of parentheses “()” and digits “0” through “9”. From the string $s$, you construct another string $t$ by considering every character of $s$ in order and performing the following operations based on the character values:
- ”(” : append “(” to $t$.
- ”)”: append “)” to $t$.
- $0 \leq c \leq 9$: delete any $c$ characters from $t$.
- It is guaranteed that it is always possible to do so.
- The deleted characters don’t need to be consecutive.
Is it possible to construct $t$ to be a balanced bracket sequence?
Input
The first line contains an integer $t$ ($1 \leq t \leq 10^{4}$), the number of test cases.
For each test case, you are given a non-empty string $s$ consisting of parentheses and digits (”()0123456789”).
The length of the string will be at most $3 \cdot 10^{5}$ characters.
It is guaranteed that the total length of the strings will not exceed $3 \cdot 10^{5}$ characters.
Output
For each test case, output Yes if it is possible to construct $t$ to be a balanced bracket sequence, and No otherwise.
Examples
Input
2
((()(3)1
(()1)
Ieșire
Yes
No
Input
5
()1()
(())
()1((((2()())))3)()
((2))()
((1()))(1)()
Ieșire
No
Yes
Yes
No
Yes