Compare Tree Traversal Paths

There is a tree with n vertices. Choose one starting vertex, then traverse all edges by the following rules.

• Move along an edge that has not been used before.
• If several unused edges are available, choose any one of them.
• If no unused edge is available at the current vertex, return to the previous vertex.

When the process finishes, every edge has been used exactly twice. Record 0 when a move goes farther from the starting vertex, and record 1 when a move goes closer to it. Because the order of choosing edges can differ, the same tree can be recorded as different strings.

Given two traversal strings, determine whether they could have been produced from the same tree with the same starting vertex.

The first line contains the number of data sets T. (1 ≤ T ≤ 10)

The next 2×T lines each contain one traversal string. The length of each string is at most 3,000, and each string consists only of 0 and 1. A string of length 0 represents a tree with no edges.

For each data set, print one line in input order: 1 if the two strings can represent the same tree, and 0 otherwise.