题目描述

一些大城市拥有树状结构的地铁系统（任意两站之间仅有一条路径），且大多有一个独特的中央车站。游客从中央车站出发探索地铁系统，规则如下：

1. 每次到达车站时，选择未乘坐过的线路；
2. 若无可选线路，则沿首次到达该站的线路返回；
3. 最终每条线路会被往返各走一次，回到中央车站；
4. 行程可编码为二进制字符串：0表示离中央车站更远，1表示朝中央车站靠近。

给定两个二进制字符串，判断它们是否可能是同一地铁树的探索行程。

Input

输入格式

• 首行是正整数 n，表示测试用例数量；
• 每个测试用例包含两行字符串，由 0 和 1 组成，长度≤3000，均为合法的地铁树探索行程。

输出格式

若两个字符串可对应同一地铁树，输出 same；否则输出 different。

输入样例

2  
0010011101001011  
0100011011001011  
0100101100100111  
0010001110101011  

输出样例

same  
different  

题目来源

2003 年西北欧编程竞赛