Problem E
Description
Given a string consisting of brackets of two types, find its longest substring that is a regular brackets sequence. A regular brackets sequence is defined as below:
1. an empty sequence is a regular brackets sequence;
2. if S is a regular brackets sequence, (S), [S] are both regular brackets sequences.
3. if S1 and S2 are regular brackets sequences, the concatenation of S1 and S2 is a regular brackets sequence.
For instance, [()], (([[([])]])), ()[()] are all regular brackets sequences. Note that a substring is a continuous section of the original string.
Input
There are multiple test cases in the input. The first line of the input contains a single integer N (0 < N < 20), which is the number of the test cases. Each test case contains a string containing only characters ‘(’ , ‘)’ , ‘[’ and ‘]’ . The length of the string does not exceed 100,000.
Output
For the given string in each test case, output the length of its longest substring that is a regular brackets sequence in a single line.
Note that a brute force method will exceed the time limit.
Sample Input
3
([(][()]]()
([)]
()[]()[])()[]))[](((())))[](((())))
Sample Output
4
0
20