#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 21092013;

int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int mult(int a, int b)
{
	return (LL)a * b % mod;
}
int binpow(int a, int p)
{
	int ans = 1;
	while (p)
	{
		if (p & 1) ans = mult(ans, a);
		a = mult(a, a);
		p /= 2;
	}
	return ans;
}

void solve()
{
	string S, t;
	cin >> S >> t;
	string s = "";
	FOR (i, 0, SZ(S))
	{
		if (S[i] == 'U')
		{
			if (!s.empty())
				s.pop_back();
		}
		else
			s.PB(S[i]);
	}
	int n = SZ(t);
	VI l(n), r(n), u(n);
	FOR (i, 0, n)
	{
		if (t[i] == 'L')
			l[i] = 1;
		if (t[i] == 'R')
			r[i] = 1;
		if (t[i] == 'U')
			u[i] = 1;
		if (i)
		{
			u[i] += u[i - 1];
			l[i] += l[i - 1];
			r[i] += r[i - 1];
		}
	}
	int ans = 0;
	FOR (cnt, 1, SZ(s) + 1)
	{
		int j = lower_bound(ALL(u), cnt) - u.begin();
		if (j == n)
			break;
		ans = add(ans, 1);
		if (s[SZ(s) - cnt] == 'R')
			j = lower_bound(ALL(l), l[j] + 1) - l.begin();
		else
			j = lower_bound(ALL(r), r[j] + 1) - r.begin();
		if (j == n)
			continue;
		int pw = l[n - 1] - l[j] + r[n - 1] - r[j];
		ans = add(ans, binpow(2, pw));
	}
	int pw = l[n - 1] + r[n - 1];
	ans = add(ans, binpow(2, pw));
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	FOR (tc, 0, t)
	{
		cout << "Case " << tc + 1 << ": ";
		solve();
	}
	
	return 0;
}