给定一个由括号（“(” 和 “)”）和数字（“0” 到 “9”）组成的字符串 $s$。通过按顺序考虑 $s$ 中的每个字符并根据字符值执行以下操作，你可以构造另一个字符串 $t$：

• “(”：将 “(” 追加到 $t$。
• “)”：将 “)” 追加到 $t$。
• $0 \le c \le 9$：从 $t$ 中删除任意 $c$ 个字符。保证此操作总是可行的。被删除的字符不需要是连续的。

请问是否可以将 $t$ 构造为一个合法的括号序列？

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。

对于每个测试用例，给定一个由括号和数字（“()0123456789”）组成的非空字符串 $s$。字符串的长度最多为 $3 \cdot 10^5$。

保证所有测试用例的字符串总长度不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，如果可以将 $t$ 构造为合法的括号序列，则输出 “YES”，否则输出 “NO”。

你可以以任何大小写形式输出每个字母。例如，“yEs”、“yes”、“Yes” 和 “YES” 都将被视为肯定的回答。

样例

输入格式 1

2
((()(3)1
(()1)

输出格式 1

Yes
No

输入格式 2

5
()1()
(())
()1((((2()())))3)()
((2))()
((1()))(1)()

输出格式 2

No
Yes
Yes
No
Yes