Balanced Sequence After Replacement

Given a string of length 'N' containing only the characters: '[', '{', '(', ')', '}', ']'. At certain places, the character 'X' appears in place of any bracket. Your goal is to determine if replacing all the 'X's with suitable brackets can result in a valid balanced sequence.

Example:

Input:

"[X)](X"
 "[XX{"

Output:

Valid
Invalid

Explanation:

For the string "[X)](X", replacing the first X with '(' and the second X with ')' results in the sequence "[()]()", which is a valid balanced sequence. However, for the string "[XX{", no replacement will result in a valid bracket sequence.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 20
• Time limit: 1 sec

Input:

The first line contains an integer 'T' indicating the number of test cases. Each of the following T lines contains a single string to be evaluated.

Output:

For each test case, output "Valid" if a balanced sequence can be achieved after replacing all 'X's, otherwise output "Invalid".

Note:

In the function, return 'True' for a valid string and 'False' for an invalid string without printing.