描述

以下文法描述了一种带有（不一定唯一）顶点标签的树的文本表示法：

树 ::= 标签

树 ::= 标签 ( 子树列表 )

子树列表 ::= 树

子树列表 ::= 子树列表 , 树

标签 ::= A | B | C | … | Z

也就是说，一棵树的表示由一个标签（是一个大写字母）或者一个标签后跟一个用括号括起来的、由逗号分隔的有序树列表组成。

为了在纸上绘制这样一棵树，我们必须在页面上写出每个标签，使得一个顶点的子树的标签围绕该顶点按逆时针方向排列。这些标签的位置必须使得用不相交的线段将每个顶点与其每个子树连接起来。也就是说，我们绘制树的常规平面表示形式，同时保留子树的顺序。除了这些限制之外，该表示的位置、形状和大小是任意的。

例如，$A(B(C,D),E)$ 的一种可能的图形表示如下：

给定两棵树的文本表示，你需要确定它们是否等价。也就是说，它们是否具有相同的纸上表示形式？

输入

输入的第一行包含 $t$，即测试用例的数量。每个测试用例由两行组成，每行以上述表示法指定一棵树。每行最多包含 $200$ 个字符，且不包含空白字符。

输出

对于每个测试用例，根据情况输出包含 “same” 或 “different” 的一行。

输入数据 1

2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))

输出数据 1

different
same

来源

滑铁卢当地 2004 年 9 月 25 日