Longest Balanced Bracket Substring

You are given a string s containing only round brackets (' , ') and square brackets [, ]. Your task is to determine the length of the longest contiguous substring which forms a balanced sequence of brackets. A sequence is considered balanced if every opening bracket has a matching closing bracket and the pairs of brackets are properly nested.

Note: The substring must be contiguous.

The problem requires careful scanning of the string using an appropriate data structure like a stack to keep track of bracket indices.

The solution involves iterating over the string and tracking the last unmatched position. If the current character is a closing bracket and there is a matching opening bracket (found using a stack), the length of the balanced substring is updated accordingly.

Use the provided examples to ensure your solution handles different cases including edge cases where the string does not have any balanced substring.

The balanced condition can be represented in LaTeX as follows: a sequence S is balanced if \[ S = \begin{cases} "" & \text{if } S \text{ is empty}, \ S = \{ (S'), [S''] \} & \text{if } S' \text{ and } S'' \text{ are balanced}, \ S = S_1S_2 & \text{if } S_1 \text{ and } S_2 \text{ are balanced} \end{cases} \] which means any valid pairing can be nested or concatenated to form a balanced sequence.

inputFormat

The first line contains an integer t (1 ≤ t ≤ 100), representing the number of test cases. Each of the following t lines contains a single string consisting of the characters '(', ')', '[' and ']'.

For example:

3
[][()]
[[]][]
[[][()]]

outputFormat

For each test case, output a single line with an integer indicating the length of the longest balanced substring.

For the input example above, the output should be:

6
6
8

## sample

3
[][()]
[[]][]
[[][()]]

6
6
8

</p>