Valid Parentheses Sequence

Given a sequence consisting solely of the characters '(' and ')', determine if the sequence is a valid parentheses sequence. A sequence is considered valid if every opening bracket has a corresponding closing bracket and the pairs are properly nested.

For example, the sequence (()()) is valid while the sequence ()()) is not valid.

Your task is to process multiple test cases. Each test case consists of a single line string representing a parentheses sequence. It is guaranteed that the input reading and output printing are done via standard input (stdin) and standard output (stdout). Use efficient stack-based parsing methods to validate the sequence.

The validation criteria can be mathematically expressed by checking that the following condition holds for every prefix of the sequence: \[ \text{balance} \ge 0, \quad \text{and finally} \quad \text{balance} = 0, \] where \( \text{balance} \) is increased by 1 for each '(' encountered and decreased by 1 for each ')' encountered.

inputFormat

The first line contains a single integer T which denotes the number of test cases.

Each of the following T lines contains a string composed of the characters '(' and ')'. Note that the empty string is also a valid test case.

outputFormat

For each test case output a single line containing "YES" if the sequence is a valid parentheses sequence, otherwise output "NO".

## sample

3
(()())
()())
((())

YES
NO
NO

</p>