함께 걷는 길

작은 마을의 길은 모두 격자 모양이다. 존과 마이크는 학교에서 집까지 부모가 정해 준 경로를 그대로 걷는다. 경로는 S, R, L로 이루어진 문자열로 주어진다. 두 사람은 학교에서 같은 방향을 보고 출발하고, 교차로마다 지시를 하나 처리한다. S는 방향을 그대로 두고, R는 오른쪽으로, L은 왼쪽으로 돈 다음, 한 블록을 걸어 다음 교차로로 간다. 예를 들어 경로가 SSRRL이면 두 블록을 직진하고, 오른쪽으로 돌아 한 블록, 다시 오른쪽으로 돌아 한 블록, 마지막으로 왼쪽으로 돌아 한 블록을 걷는다. 경로는 최단이 아니라서 같은 교차로를 여러 번 지날 수도 있다.

두 사람은 되도록 많은 블록을 나란히 걷고 싶다. 교차로에서는 원하는 만큼 기다릴 수 있지만, 자기 경로를 벗어나거나 지시 순서를 바꿀 수는 없다. 같은 교차로에 둘이 함께 서 있고 각자의 다음 한 블록이 같은 구간이면, 그 블록을 나란히 걸어 다음 교차로에 함께 도착한다. 같은 교차로를 서로 다른 시각에 지나가기만 하면 함께 걸은 것이 아니고, 함께 서 있어도 다음에 걷는 구간이 다르면 함께 걸은 것이 아니다.

존의 $i$번째 이동이 교차로 $u$에서 교차로 $v$로 가고 마이크의 $j$번째 이동도 $u$에서 $v$로 가면, 두 이동은 같은 블록이다. 모든 $t$에 대해 존의 $i_t$번째 이동과 마이크의 $j_t$번째 이동이 같은 블록이 되는 $i_1 < i_2 < \dots < i_k$와 $j_1 < j_2 < \dots < j_k$가 존재하는 가장 큰 $k$를 구한다. 이 값은 두 사람이 함께 도착할 수 있는 교차로의 개수와 같다.

첫 줄에 테스트 케이스의 수 $N$이 주어진다 ($1 \le N \le 100$). 다음 $N$개 줄에는 각각 존의 경로와 마이크의 경로가 공백 하나로 구분되어 주어진다. 두 문자열은 S, R, L로만 이루어지고, 길이는 $1$ 이상 $100$ 이하다.

각 테스트 케이스마다 한 줄에 Case #n: k를 출력한다. $n$은 $1$부터 시작하는 테스트 케이스 번호이고, $k$는 두 사람이 나란히 걸을 수 있는 블록 수의 최댓값이다.