题目背景

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

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

题目描述

使用左括号 ( 和右括号 ) 构成的字符串中，所谓“正确括号序列”定义如下：

• 仅包含一对括号的字符串 () 是一个正确的括号序列。
• 若 $X$ 是一个正确的括号序列，则用括号将 $X$ 包起来形成的 $(X)$ 也是一个正确的括号序列。
• 若 $X$ 和 $Y$ 都是正确的括号序列，则将它们连接而成的 $XY$ 也是一个正确的括号序列。
• 所有正确的括号序列都只能通过以上三条规则构造出来。

例如，((()(()))) 和 (())()() 是正确的括号序列，而 (() 或 )((()() 都不是正确的括号序列。

对于一个正确的括号序列 $X$，我们定义其括号值 $f[X]$，具体如下：

• $f[()] = 1$；
• 若 $X$ 是一个正确的括号序列，则 $f[(X)] = 2 \times f[X]$；
• 若 $X$ 和 $Y$ 是正确的括号序列，则 $f[XY] = f[X] + f[Y]$。

我们来看几个例子：

• $f[()] = 1$；
• $f[(())] = 2 \times f[()] = 2 \times 1 = 2$；
• $f[()()] = f[()] + f[()] = 1 + 1 = 2$；
• $f[()()()] = f[()] + f[()()] = 1 + 2 = 3$；
• $f[(()())] = 2 \times f[()()] = 2 \times 2 = 4$；
• $f[((()))] = 2 \times f[(())] = 2 \times 2 = 4$；
• $f[()(())] = f[()] + f[(())] = 1 + 2 = 3$；
• $f[(()())()(())] = f[(()())] + f[()(())] = 4 + 3 = 7$。

你的任务是读取两个正确的括号序列 $A$ 和 $B$，比较它们的括号值 $f[A]$ 与 $f[B]$。

也就是说，判断 $f[A] = f[B]$、$f[A] < f[B]$ 还是 $f[A] > f[B]$。

一个输入中会包含 $T$ 个测试用例。

输入格式

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

接下来的 $T$ 个测试用例中，每个测试用例如下两行组成：

• 第一行为括号序列 $A$；
• 第二行为括号序列 $B$。

输出格式

对于每个测试用例，输出一行结果：

• 若 $f[A] = f[B]$，输出等号 =；
• 若 $f[A] < f[B]$，输出小于号 <；
• 若 $f[A] > f[B]$，输出大于号 >。

1
(())
()()

=

1
()()()
(()())

<

2
((()))
()(())
(((())))
()()()()()

>
>

提示

样例 1 说明

$f[A] = f[(())] = 2$，$f[B] = f[()()] = 2$，因此 $f[A] = f[B]$。

样例 2 说明

$f[A] = f[()()()] = 3$，$f[B] = f[(()())] = 4$，因此 $f[A] < f[B]$。

样例 3 说明

• 第一个测试用例中，$f[A] = f[((()))] = 4$，$f[B] = f[()(())] = 3$，因此 $f[A] > f[B]$。
• 第二个测试用例中，$f[A] = f[(((())))] = 8$，$f[B] = f[()()()()()] = 5$，因此 $f[A] > f[B]$。

约束条件

• $1 \leq T \leq 10$
• $A$ 和 $B$ 都是正确的括号序列。
• 一个输入中所有测试用例中 $A$ 的总长度之和不超过 $3\times10^6$。
• 一个输入中所有测试用例中 $B$ 的总长度之和不超过 $3\times10^6$。

子任务

1. （$3$ 分）$A$ 和 $B$ 的长度都不超过 $6$。
2. （$23$ 分）$A$ 和 $B$ 的长度都不超过 $50$。
3. （$13$ 分）
   • 括号数量相等，且所有右括号都出现在所有左括号之后的括号序列，称为“简单括号序列”。
     • 例如 ()、(())、((()))、(((((()))))) 都是简单括号序列。
   • $A$ 和 $B$ 都是由长度各不相同的多个简单括号序列拼接而成的。
     • 比如 ()(())、(((())))()((())) 是符合的例子。
     • (())()(()) 也是由简单括号序列拼接而成，但因为包含了两段长度相同的简单括号序列 (())，因此在此子任务中不会出现这种情况。
4. （$61$ 分）无额外约束条件。