Valid String Problem Statement

You are provided with a string S containing only three types of characters: ('), )'), and *.

Explanation:

A Valid String is characterized by the following conditions:

1. Each left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Each right parenthesis ')' must have a corresponding left parenthesis '('.
3. A left parenthesis '(' must appear before its corresponding right parenthesis ')'.
4. The asterisk '*' can be considered as either a right parenthesis ')', a left parenthesis '(', or an empty string.
5. An empty string is considered valid.

Your task is to determine whether the given string is a Valid String.

Input:

The first line contains an integer 'T' representing the number of test cases. Each test case consists of a single line with the string 'S'.

Output:

For each test case, output 'Yes' if the string 'S' is valid; otherwise, output 'No'. Each result should be printed on a new line.

Example:

Input:

T = 2
S = "()"
S = "(*)"

Output:

Yes
Yes

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000
• Where N is the length of the string S.

Note:

You need to implement the function only, the I/O is handled already.