무한 이진 트리 이동

이진 트리는 모든 노드가 자식을 최대 두 개까지 갖는 트리 자료 구조다. 두 자식은 보통 왼쪽 자식과 오른쪽 자식으로 구분하고, 자식을 갖는 노드를 그 자식의 부모라고 한다.

지시 문자열은 L, R, U로만 이루어진 문자열이다. L은 왼쪽, R은 오른쪽, U는 위를 뜻한다.

상현이는 무한 이진 트리를 그렸다. 이 트리에서는 모든 노드에 자식이 둘 있고, 모든 노드에 부모가 있다. 루트의 부모는 루트 자신이다. 상현이는 루트에서 출발해 김숭이 보낸 지시 문자열 $S$를 앞에서부터 한 글자씩 따라가며 트리를 이동한다. L은 왼쪽 자식으로, R은 오른쪽 자식으로, U는 부모로 이동한다는 뜻이다.

$S$를 따라 이동을 시작하려는 순간 강수가 지시 문자열 $T$를 보냈다. 상현이는 $S$를 끝까지 따라간 직후 곧바로 $T$를 따라 이동한다. 다만 $S$를 따라가면 많이 지치기 때문에 $T$의 글자 중 일부는 건너뛸 수도 있다. 건너뛰는 글자는 몇 개든 어느 자리든 마음대로 고르고, 남은 글자는 원래 순서대로 따라간다. 이동이 끝날 수 있는 노드가 모두 몇 개인지 구하자.

예를 들어 $S$가 L이고 $T$가 LU면 답은 $3$이다. $S$를 따라가면 루트의 왼쪽 자식에서 멈추고, 여기서 $T$를 따라 이동하는 방법은 네 가지다.

1. $T$의 두 글자를 모두 건너뛰면 루트의 왼쪽 자식에서 멈춘다.
2. L을 건너뛰면 루트에서 멈춘다.
3. U를 건너뛰면 루트의 왼쪽 자식의 왼쪽 자식에서 멈춘다.
4. 아무 글자도 건너뛰지 않으면 루트의 왼쪽 자식에서 멈춘다.

네 가지 중 두 가지가 같은 노드에서 멈추므로, 서로 다른 노드는 $3$개다.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. ($N \le 15$)

각 테스트 케이스는 두 줄이다. 첫째 줄에 지시 문자열 $S$, 둘째 줄에 지시 문자열 $T$가 주어진다. 두 문자열은 L, R, U로만 이루어져 있고, 길이는 $100000$을 넘지 않는다.

각 테스트 케이스마다 한 줄에 Case i: x 형식으로 출력한다. $i$는 $1$부터 시작하는 테스트 케이스 번호이고, $x$는 이동이 끝날 수 있는 서로 다른 노드의 개수다. 답이 매우 커질 수 있으므로 $x$는 $21092013$으로 나눈 나머지를 출력한다.