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 strings. For each string, , output on the th line, the validity of the th string. If the string is valid, output
YES. If the string is invalid, output
NO. The length in characters of each string, , is guaranteed to be in the range .
In all tests,
The first line contains one number, .
The following lines each contain one string .
Output the validity of the th string on the th line.
7 1(2) (1)(2) ((1))(2) (500()) (12 (1)) ((1)()
YES YES YES YES NO NO NO