Valid Parentheses Checker

Given a list of strings each composed only of the characters ( and ), determine whether each string is a valid sequence of parentheses.

A string is considered valid if every opening parenthesis ( has a corresponding closing parenthesis ) and the pairs are correctly nested. The standard algorithm involves using a stack to keep track of unmatched opening parentheses: when a closing parenthesis is encountered, it must match the most recent unmatched opening one. If at the end the stack is empty, the sequence is valid.

Your task is to implement a solution that reads an integer n from standard input (which represents the number of test strings), then reads n strings. For each string, output True if the string is valid and False otherwise.

inputFormat

The input is read from stdin and consists of:

• A single integer n on the first line, representing the number of test strings.
• The following n lines, each containing a string of parentheses. Note that a line could be an empty string, which is considered valid.

outputFormat

For each test string, print a line to stdout containing either True or False. Each output should be in the same order as the input test strings.

## sample

3
()
(())
()()

True
True
True

</p>