A Walk Together

Every road in a small town runs along a grid. John and Mike each walk a fixed route from school to home, given to them by their parents. A route is a string of S, R, and L. Both leave the school facing the same direction, and at every intersection each of them handles one instruction: S keeps the current direction, R turns right, L turns left, and then the walker crosses one block to the next intersection. For the route SSRRL John walks two blocks straight, turns right and walks one block, turns right again and walks one block, then turns left and walks one block. Routes are not optimized, so the same intersection can be visited more than once.

The two want to walk side by side for as many blocks as they can. Either of them can wait at an intersection as long as needed, but neither leaves his own route or reorders his instructions. When both stand at the same intersection and each of their next blocks is the same stretch of road, they walk that block side by side and arrive at the next intersection together. Passing the same intersection at different moments does not count as walking together, and standing at the same intersection does not count when their next blocks differ.

John's $i$-th move and Mike's $j$-th move are the same block when both run from intersection $u$ to intersection $v$. Find the largest $k$ for which there are indices $i_1 < i_2 < \dots < i_k$ and $j_1 < j_2 < \dots < j_k$ such that John's $i_t$-th move and Mike's $j_t$-th move are the same block for every $t$. That number equals how many intersections they can reach together.

The first line has the number of test cases $N$ ($1 \le N \le 100$). Each of the next $N$ lines has John's route and Mike's route, separated by one space. Both strings consist of S, R, and L only, and each has length between $1$ and $100$.

For each test case print one line Case #n: k, where $n$ is the test case number starting from $1$ and $k$ is the largest number of blocks John and Mike can walk side by side.