#include <bits/stdc++.h>
using namespace std;

const int MOD = 21092013;

int L[100010], R[1000010];
int f[100010];

int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for (int cas = 1; cas <= T; cas++) {
		string S, A;
		cin >> S;
		for (int i = 0; i < S.size(); i++) {
			if (S[i] == 'U' && A != "") A.pop_back();
			if (S[i] == 'L' || S[i] == 'R') A += S[i];
		}
		cin >> S;
		int n = S.size();
		f[n] = 0;
		L[n] = R[n] = n;
		for (int i = n - 1; i >= 0; i--) {
			L[i] = (i + 1 < n && S[i + 1] == 'L') ? i + 1 : L[i + 1];
			R[i] = (i + 1 < n && S[i + 1] == 'R') ? i + 1 : R[i + 1];
			f[i] = (f[L[i]] + f[R[i]] + 1) % MOD;
		}
		int ans = f[0];
		if (S[0] == 'L') ans = (ans + 1 + f[R[0]]) % MOD;
		if (S[0] == 'R') ans = (ans + 1 + f[L[0]]) % MOD;
		for (int i = 0; i < n; i++) {
			if (S[i] != 'U') continue;
			if (A == "") break;
			ans = (ans + 1 + f[R[i]] * (A.back() == 'L') + f[L[i]] * (A.back() == 'R')) % MOD;
			A.pop_back();
		}
		printf("Case %d: %d\n", cas, ans);
	}
	return 0;
}