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:

1. Nothing (an empty string).
2. A non-negative integer expressed in decimal digits (e.g. 5, 230, 0032), optionally followed by another valid string.
3. A pair of brackets enclosing a valid string (e.g. (5)), also optionally followed by another valid string.

Examples of valid strings:
(1)(2), ((1))(2), 1(2), (500())

Examples of invalid strings:
(12, (1)), ((1)()

You are given ~N~ strings. For each string, ~s_1, s_2, \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]~.

Constraints

In all tests,
~1 \le N \le 100~

Input Specification

The first line contains one number, ~N~.
The following ~N~ lines each contain one string ~s_i~.

Output Specification

Output the validity of the ~i~th string on the ~i~th line.

Sample Input

7
1(2)
(1)(2)
((1))(2)
(500())
(12
(1))
((1)()

Sample Output

YES
YES
YES
YES
NO
NO
NO