Remove Invalid Parentheses

Given a string containing only parentheses and letters, your goal is to remove the minimum number of invalid parentheses to make the input string valid and return all possible valid strings.

Input:

The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single string ‘STR’ representing the parentheses and letters.

Output:

For each test case, return all possible unique valid strings obtained after removing the minimum number of parentheses. Each test case output should be printed in a separate line.

Example:

Input:

T = 2
STR = "()())()"
STR = "(a)())()"

Output:

["()()()", "(())()"]
["(a)()()", "(a())()"]

Constraints:

• 1 <= T <= 5
• 1 <= |STR| <= 50
• Time Limit: 1 second

Note:

A string is valid if every left parenthesis has a corresponding right parenthesis in the same order. Example: 'STR' = "(())())" is not valid, but 'STR' = "(())()" is valid.