Veshy is entering strings into his calculator consisting of only
), and decimal digits; however, some strings are invalid and produce an error.
A valid string must either be:
- Nothing (an empty string).
- A non-negative integer expressed in decimal digits (e.g.
0032), optionally followed by another valid string.
- A pair of brackets enclosing a valid string (e.g.
(5)), also optionally followed by another valid string.
Examples of valid strings:
Examples of invalid strings:
You are given ~N~ strings. For each string, ~s_1, s_2, s_3, \dots, s_N~, output on the ~i~th line, the validity of the ~i~th string. If the string is valid, output
YES. If the string is invalid, output
NO. The length in characters of each string, ~s_i~, is guaranteed to be in the range ~[1,1000]~.
In all tests,
~1 \le N \le 100~
The first line contains one number, ~N~.
The following ~N~ lines each contain one string ~s_i~.
Output the validity of the ~i~th string on the ~i~th line.
7 1(2) (1)(2) ((1))(2) (500()) (12 (1)) ((1)()
YES YES YES YES NO NO NO