Given two trees, you have to find whether they are same or not. A tree is a connected graph with no cycles.
In this problem a tree is described as a sequence of zeroes and ones. Initially you are on the root of the tree. If you get a 1, you declare a new node and you go to that node. The parent node of this node is the node you came from. If you get a 0, you will return back to its parent node. The trees will be given such that after traversing all the nodes, you will return back to the root.
The given tree in Fig 1 can be described in two ways.
- 1011010100
- 1101010010
In this problem you are given two trees. You have to determine whether they are same or not. Two trees will be same if we start from their roots, we will get same shaped trees.
Input
Input starts with an integer T (≤ 50), denoting the number of test cases.
Each case contains two lines. In each line, a string will be given as a tree configuration. You may safely assume that the trees are valid and the length of any string will be between 0 and 10000 (inclusive). You may also assume that the length of both the trees will be same.
Output
For each case print the case number and Same or Different depending on whether the trees are same or not.
Sample
| Sample Input | Sample Output |
|---|---|
3 1011010100 1101010010 1101010010 1011110000 | Case 1: Same Case 2: Same Case 3: Different |
Notes
The second case contains two blank lines, which denote two empty trees.