Moves on an Infinite Binary Tree

A binary tree is a tree data structure in which every node has at most two children. The two children are usually told apart as the left child and the right child, and a node that has a child is called the parent of that child.

An instruction string is a string made up only of L, R, and U. L means left, R means right, and U means up.

Sanghyun drew an infinite binary tree. Every node of this tree has two children, and every node has a parent. The parent of the root is the root itself. Starting at the root, Sanghyun walks the tree by following the instruction string $S$ that Kimsung sent him, one letter at a time. L moves to the left child, R moves to the right child, and U moves to the parent.

Just as he is about to start on $S$, Gangsu sends another instruction string $T$. Sanghyun follows $S$ to its end and then immediately follows $T$. Following $S$ leaves him worn out, so he may skip some of the letters of $T$. He freely picks how many letters to skip and which ones, and he follows the letters that remain in their original order. Count the nodes where the walk can end.

For example, if $S$ is L and $T$ is LU, the answer is $3$. Following $S$ stops at the left child of the root, and from there $T$ can be followed in four ways.

1. Skipping both letters of $T$ stops at the left child of the root.
2. Skipping L stops at the root.
3. Skipping U stops at the left child of the left child of the root.
4. Skipping nothing stops at the left child of the root.

Two of the four ways stop at the same node, so the number of distinct nodes is $3$.

The first line contains the number of test cases $N$. ($N \le 15$)

Each test case takes two lines. The first line holds the instruction string $S$ and the second line holds the instruction string $T$. Both strings are made up only of L, R, and U, and neither one is longer than $100000$.

For each test case, print one line in the form Case i: x. Here $i$ is the test case number starting from $1$, and $x$ is the number of distinct nodes where the walk can end. The answer can grow very large, so print $x$ modulo $21092013$.