Valid String Problem Statement

Given a string S consisting solely of the characters '(', ')', and '*', determine if it is a valid string.

Definition of Valid String:

1. Every left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Every right parenthesis ')' must have a corresponding left parenthesis '('.
3. A left parenthesis '(' must occur before the corresponding right parenthesis ')'.
4. The character '*' can represent a single left parenthesis '(', a single right parenthesis ')', or an empty string.
5. An empty string is also considered valid.

Objective:

For each provided test case, ascertain whether the string S is valid and print 'Yes' or 'No' as the outcome.

Input:

The first line contains an integer 'T', the number of test cases. Each of the following T lines contains one string 'S'.

Output:

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

Example:

Input:

2
()
(*)))

Output:

Yes
No

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000, where 'N' is the length of string 'S'.
• Time Limit: 1 sec