Binary Tree is a tree data structure where each node has at most two children, usually they are distinguished as left and right child. And the node having the children are called parent of those children. An instruction string is a string consisting of the letters \textbf{L}, \textbf{R} and \textbf{U}. \textbf{L} stands for Left, \textbf{R} for Right and \textbf{U} for Up. Meaning of these will be clear shortly. One day I have drawn 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 consider the parent of the root is root itself. I put a pen in the root and follow the instruction string \textbf{S}. That is, we look at the first character if it says \textbf{L} we go to left child, if it says \textbf{R} we go to right child and if it says \textbf{U} then to the parent. If we receive a \textbf{U} instruction at root we just end up at root since we assumed parent of the root is root itself. Now we have another instruction string \textbf{T}. Starting from the node where we are after following the instruction string \textbf{S}, we will follow the instruction string \textbf{T}. But this time, if we wish we may skip any instruction in the string \textbf{T} (possibly discarding all of them). You have to tell me how many different nodes I can end up after following instruction string \textbf{T} (skipping as many instructions as I wish). For example: Suppose: \textbf{S} = \textbf{L} and \textbf{T} = \textbf{LU}. Our answer is \textbf{3}. Following \textbf{S} we will end up at the left child of the root. Now, when we follow \textbf{T}, there may be \textbf{4} cases: \begin{enumerate} \item Skipping all letters: we will be at the same node where we are. \item Skipping \textbf{L} and following \textbf{U}: we will be at the root. \item Following \textbf{L} and Skipping \textbf{U}: we will be at the left child of current node. \item Following both \textbf{L} and \textbf{U}: we will be at the same node as in case \textbf{1}. \end{enumerate} Since \textbf{3} different nodes we can end up after following \textbf{T}, the answer is \textbf{3}. \InputFile First line contains the number of test cases \textbf{n} (\textbf{n }≤ \textbf{15}). Hence follow \textbf{n} test cases. Each test case consists of two non empty strings. First line will contain instruction string \textbf{S} and the second line will contain the instruction string \textbf{T}. You may assume that there will not be any letter other than \textbf{L}, \textbf{R} or \textbf{U} in these strings. Length of the strings will not be greater than \textbf{100000}. \OutputFile 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 \textbf{21092013}.