Remove Invalid Parentheses

You are given a string consisting only of parentheses and letters. Your task is to remove the minimum number of invalid parentheses and return all possible unique, valid strings thus obtained.

Note:

1) A string is valid only if every left parenthesis has corresponding right parentheses in the same order.

For example Given ‘STR’ = (())()) is not a valid string, whereas ‘STR’ = (())() is a valid string.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first and the only line of each test case contains a single string ‘STR’ representing the parenthesis.

Output Format:

For each test case, return all possible unique, valid strings after removing the minimum number of parentheses. 

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= |STR| <= 50

Time Limit: 1 second

Sample Input 1:

2
(((a))()
)(()))

Sample Output 1:

(((a))) ((a))()
(())

Explanation of Sample Output 1:

Test Case 1 :  
Given ‘STR’ = (((a))()
From this string, two valid strings can be generated after removing only one parenthesis, which is minimum.
One way is to remove the parenthesis at index 6 to generate (((a))).
Another way is to remove either the first, second, or third parenthesis, which will result in the same string, i.e., ((a))().

Test Case 2 : 
Given ‘STR’ = )(()))
The minimum number of invalid parentheses required to be removed is 2. We have to remove the first and last parentheses to generate a valid string.
So the valid string is (()).

Sample Input 2:

1
(()(()(())

Sample Output 2:

()()(()) ()(()()) (())(()) (()()()) (()(()))