Metro
Some cities have a metro network structured like a tree, meaning there is exactly one path between any two stations. These networks have a unique central station. Imagine you are a tourist in such a city, eager to explore the entire metro network. You start at the central station, randomly choose a direction, and travel to the next station. Each time you reach a station, you select one of the branches you haven't traveled on yet. If no unexplored branches remain at a station, you return to the station from which you first arrived. This process continues until you have traveled all branches twice (once in each direction). At this point, you will be back at the central station. Such a journey can be represented as a binary string: the digit **0** represents a trip moving away from the central station, and the digit **1** represents a trip moving closer to the central station. Multiple encoding strings can represent the same metro network since "unexplored" branches are chosen randomly.
Write a program to determine whether two binary strings describe the same metro network.
Input
The first line of the input contains an integer **N** (1 ≤ **N** ≤ 20) - the number of test cases. Following this are **N** pairs of strings, each consisting of the digits **0** and **1**, with a maximum length of 3000 characters.
Each line encodes one valid exploration of the metro network.
Output
For each pair of strings, print "same" if both strings encode the exploration of the same metro network, or "different" if the explored metro networks are different.