题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定两个仅由左括号 ( 和右括号 ) 组成的字符串 $A$ 和 $B$。

我们定义 $S(A, B)$ 为以下所有字符串的集合：

• 是 $A$ 的子串；
• 是 $B$ 的子串；
• 并且是一个合法括号序列；
• 集合中元素互不相同。

请你判断 $S(A, B)$ 是否为空集。如果不是，请计算出 $S(A, B)$ 中最长字符串的长度。

你需要解决一个输入中给出的 $T$ 个测试用例。

合法括号序列的定义

合法括号序列的定义如下：

• 单独的一对括号 () 是合法括号序列；
• 若 $X$ 是合法括号序列，则用括号将其包围后的 $(X)$ 也是合法括号序列；
• 若 $X$ 和 $Y$ 都是合法括号序列，则其连接后的 $XY$ 也是合法括号序列；
• 所有合法括号序列都只能通过以上三种规则构造。

例如：((()(()))) 和 (())()() 是合法括号序列，而 (() 和 )((()() 都不是合法括号序列。

子串的定义

给定一个长度为 $l$ 的字符串 $s$，以及满足 $1 \leq i \leq j \leq l$ 的两个整数 $i$ 和 $j$，则 $s[i..j]$ 表示从第 $i$ 个字符开始到第 $j$ 个字符为止的连续子串。

例如若 $s = \texttt{()(()()}$，则 $s[3..5] = \texttt{(()}$，$s[4..7] = \texttt{()()}$，因此 (() 和 ()() 都是该字符串的子串。但 )()( 不是其子串。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

接下来 $T$ 行，每行由两个字符串 $A$ 和 $B$ 组成，中间以一个空格隔开，表示一个测试用例。

输出格式

对于每个测试用例，按顺序输出一行：

• 若 $S(A, B)$ 是空集，输出 $0$
• 否则，输出 $S(A, B)$ 中最长字符串的长度

3
()((())) (()((())))()
))(()(((( )())))))(
())) )))))(())

8
2
2

提示

约束条件

设 $\sum |A|$ 表示输入中所有测试用例的字符串 $A$ 的总长度之和，$\sum |B|$ 定义相同。

• $1 \leq T \leq 500\,000$
• 每个字符串 $A$ 和 $B$ 均由 '(' 和 ')' 构成，长度均不少于 1
• $\sum |A| \leq 500\,000$
• $\sum |B| \leq 500\,000$

子任务

1. （5 分）$\sum |A| \leq 100$，$\sum |B| \leq 100$
2. （13 分）$\sum |A| \leq 1\,000$，$\sum |B| \leq 1\,000$
3. （23 分）$\sum |A| \leq 10\,000$，$\sum |B| \leq 10\,000$
4. （17 分）所有测试用例中均满足 $A = B$
5. （42 分）无额外约束条件