二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。拥有子节点的节点被称为这些子节点的父节点。

指令字符串是由字母 L、R 和 U 组成的字符串。L 代表左（Left），R 代表右（Right），U 代表上（Up）。这些指令的含义很快就会明了。

有一天，我画了一棵无限大的二叉树。在这棵树中，每个节点都有两个子节点（左子节点和右子节点），且每个节点都有一个父节点。对于本题，我们认为根节点的父节点就是根节点本身。我将笔放在根节点上，并按照指令字符串 $S$ 进行移动。也就是说，我们查看第一个字符，如果它是 L，我们就移动到左子节点；如果它是 R，我们就移动到右子节点；如果它是 U，我们就移动到父节点。如果在根节点收到 U 指令，我们仍停留在根节点，因为我们假设根节点的父节点是根节点本身。

现在我们有另一个指令字符串 $T$。从按照指令字符串 $S$ 移动后所在的节点开始，我们将执行指令字符串 $T$。但这一次，我们可以选择跳过字符串 $T$ 中的任意指令（甚至可以丢弃所有指令）。你需要告诉我，在执行指令字符串 $T$ 后（可以随意跳过其中的指令），我最终可能到达多少个不同的节点。

例如： 假设 $S = \text{L}$ 且 $T = \text{LU}$。我们的答案是 3。执行 $S$ 后，我们将到达根节点的左子节点。现在，当我们执行 $T$ 时，有 4 种情况： i 跳过所有字母：我们停留在当前节点。 ii 跳过 L 并执行 U：我们将到达根节点。 iii 执行 L 并跳过 U：我们将到达当前节点的左子节点。 iv 同时执行 L 和 U：我们将到达与情况 i 相同的节点。 由于我们最终可以到达 3 个不同的节点，因此答案是 3。

输入格式

测试文件的第一行包含一个整数 $N$ ($N \le 15$)，表示测试用例的数量。接下来是 $N$ 个测试用例。每个测试用例包含两个非空字符串。第一行包含指令字符串 $S$，第二行包含指令字符串 $T$。你可以假设这些字符串中不会出现 L、R 或 U 以外的字母。字符串的长度不超过 $100000$。

输出格式

对于每个测试用例，输出用例编号，后跟最终可能到达的节点数量。由于答案可能很大，你需要将答案对 $21092013$ 取模。

样例

输入 1

2
L
LU
L
L

输出 1

Case 1: 3
Case 2: 2