Hide

Problem H
Binary Tree

A Binary Tree is a tree data structure where each node has at most two children, distinguished as left and right child, and the node having the children is called the parent of those children.

An instruction string is a string consisting of the letters L, R and U. L stands for Left, R for Right and U for Up. The meaning of these will be clear shortly.

One day I drew an infinitely large Binary Tree. In this tree each node has exactly two children (left child and right child), and each of them has a parent. For this problem, we will assume that the parent of the root is root itself. We are going to put a pen in the root and follow the instruction string $S$. That is, we look at the first character, and if it says L we go to the left child, if it says R we go to the right child and if it says U then to the parent. If we receive a U instruction at root we just end up at the root since we assumed that the parent of the root is the root itself.

Now we have another instruction string $T$. Starting from the node where we are after following the instruction string $S$, we will follow the instruction string $T$. But this time, if we wish we may skip any instruction in the string $T$ (possibly discarding all of them). You have to tell me how many different nodes I can end up after following the instruction string $T$ (skipping as many instructions as I wish).

For example:

Suppose that $S = \texttt{L}$ and $T = \texttt{LU}$. Following $S$ we will end up at the left child of the root. Now, when we follow $T$, there may be $4$ cases:

  1. Skipping all letters: we will be at the same node where we are.

  2. Skipping L and following U: we will be at the root.

  3. Following L and Skipping U: we will be at the left child of current node.

  4. Following both L and U: we will be at the same node as in case $1$.

Since we can end up at $3$ different nodes after following $T$, the answer is $3$.

Input

The first line of the test file contains an integer $N$ ($1 \leq N \leq 15$) denoting number of test cases. Hence follow $N$ test cases.

Each test case consists of two non empty strings. The first line contains the instruction string $S$ and the second line contains the instruction string $T$. You may assume that there is not any letter other than L, R or U in these strings. The length of the strings is not greater than $100\, 000$.

Output

For each test case print the case number followed by the number of nodes we can end up finally. Since the answer may be large, you have to give the answer modulo $21\, 092\, 013$.

Sample Input 1 Sample Output 1
2
L
LU
L
L
Case 1: 3
Case 2: 2

Please log in to submit a solution to this problem

Log in