시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 40 12 9 47.368%

문제

바이너리 트리는 트리 자료 구조로 각 노드가 최대 2개의 자식을 갖는다. 보통 두 자식은 왼쪽 자식과 오른쪽 자식으로 구분한다. 자식을 갖는 노드는 그 자식의 부모라고 한다.

지시 문자열은 문자열 L, R, U로만 이루여져 있는 문자열이다. L은 왼쪽, R은 오른쪽, U는 위를 의미한다.

어느날 상현이는 무한 바이너리 트리를 그리고 있었다. 이 트리의 모든 노드는 두 개의 자식을 갖으며, 모든 노드는 부모를 갖는다. 루트의 부모는 루트 그 자신이 된다. 그 다음 김숭이 보내준 지시 문자열 S을 이용해 트리를 이동하려고 한다. L은 왼쪽 자식, R은 오른쪽 자식, U는 부모로 이동하는 것을 의미한다.

김숭이 보내준 문자열 S를 이용해 트리를 이동하려고 하는 순간, 강수가 지시 문자열 T를 보내줬다. 상현이는 S를 이용해 트리를 이동한 후 그 즉시 T를 이용해 트리를 이동하려고 한다. 하지만, 상현이는 S를 이용해 이동하면 매우 지친 상태가 될 수 있기 때문에, T의 문자열 중 일부는 스킵할 수도 있다. 이 때, 이동이 끝나는 노드의 개수를 구해보자.

예를 들어, S = L, T = LU인 경우 답은 3이다. S를 이용해 이동하면 루트의 왼쪽 자식에서 이동을 마치게 되고, 이제 T를 이용하면 다음과 같은 4가지 경우가 생긴다.

  1. T의 모든 글자를 스킵하는 경우 루트의 왼쪽 자식에서 이동을 마치게 된다.
  2. L을 스킵하는 경우에는 루트에서 이동을 마치게 된다.
  3. U를 스킵하는 경우에는 루트의 왼쪽 자식의 왼쪽 자식에서 이동을 마치게 된다.
  4. L과 U를 모두 스킵하지 않는 경우에는 루트의 왼쪽 자식에서 이동을 마치게 된다.

T를 이용해 이동을 마친 후 가능한 최종 노드의 수는 3개이다.

입력

첫째 줄에 테스트 케이스의 개수 N(≤15)가 주어진다. 각 테스트 케이스는 두 개의 문자열로 이루어져 있으며, 길이는 100000을 넘지 않는다. 첫째 줄에는 문자열 S, 둘째 줄에는 문자열 T가 주어지며, 모두 L, R, U로만 이루어져 있다.

출력

각 테스트 케이스 마다 이동을 마칠 수 있는 노드의 개수를 출력한다. 답이 매우 커질 수 있기 때문에 21092013으로 나눈 나머지를 출력한다.

예제 입력

2
L
LU
L
L

예제 출력

Case 1: 3
Case 2: 2

힌트