Longest Common Balanced Substring

Two strings A and B, each made only of ( and ), are given.

Let $S(A, B)$ be the set of distinct strings that are substrings of both A and B and are valid bracket sequences.

Write a program that determines whether $S(A, B)$ has at least one element. If it does, find the length of the longest string in $S(A, B)$.

You must solve T test cases from one input.

The first line contains the number of test cases T.

Each of the next T lines contains two strings A and B, separated by a single space.

For each test case, print one line in the given order.

• If $S(A, B)$ is empty, print 0.
• Otherwise, print the length of the longest string in $S(A, B)$.

$\sum |A|$ is the total length of all A in one input, and $\sum |B|$ is the total length of all B in one input.

• $1 \le T \le 500\,000$
• Each of A and B is a string of length at least 1, made only of opening and closing brackets.
• $\sum |A| \le 500\,000$
• $\sum |B| \le 500\,000$

Valid bracket sequence

A valid bracket sequence is defined as follows.

• The string () made of one pair of brackets is a valid bracket sequence.
• If X is a valid bracket sequence, then (X) is also a valid bracket sequence.
• If X and Y are valid bracket sequences, then their concatenation XY is also a valid bracket sequence.
• Every valid bracket sequence is built only by the three rules above.

For example, (()(())) and (())()() are valid, but (() and )((()() are not.

Substring

For a string s of length l and integers $1 \le i \le j \le l$, s[i..j] is the string made of the characters from the i-th through the j-th position of s, in order. Such strings are called substrings of s.

For example, if s is ()(()(), then s[1..5] is (() and s[1..7] is ()(). So (() and ()() are substrings of ()(()(). But )()( is not a substring of ()(()().