#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1200000;

long long f[MAXN];
char s1[MAXN];

int main()
{
    freopen("2.in", "r", stdin);
	int T;
	cin>>T;
	int ttt = 0;
	while(T--){
        ttt++;
		string s, s2;
		cin>>s>>s2;
		int len1 = 0;
		memset(f, 0, sizeof(f));
		memset(s1, 0, sizeof(s1));
		for (int i = 0; i<s.size(); i++){
			if (s[i]=='U'){
				if (len1>0) len1--;
                //else break;
			}
			else{
				s1[len1++] = s[i];
			}
		}
		int ll, lr;
		int len2 = s2.size();
		ll = lr = len2;
		for (int i = s2.size()-1; i>=0; i--){
			f[i] = (f[ll]+f[lr]+1ll)% 21092013;
			if (s2[i]=='L') ll = i;
			else if (s2[i]=='R') lr = i;
		}
		ll = lr = len2;
		for (int i = 0; i<s2.size(); i++){
			if (s2[i]=='L' && ll==len2) ll = i;
			else if (s2[i]=='R' && lr==len2) lr = i;
		}
		long long res = (f[ll]+f[lr]+1)%21092013;
		int lu = 0;
		for (int i = len1-1; i>=0; i--){
			char x;
			if (s1[i]=='R') x = 'L';
			else x = 'R';
			while (s2[lu]!='U' && lu<len2) lu++;
			if (lu>=len2) break;
			if (x=='L'){
				ll = max(lu,ll);
				while (ll<len2 && s2[ll]!='L') ll++;
				res += f[ll]+1;
				res %= 21092013;
			}
			else{
				lr = max(lu,lr);
				while (lr<len2 && s2[lr]!='R') lr++;
				res += f[lr]+1;
				res %= 21092013;
			}
			lu++;
		}
		cout<<"Case "<<ttt<<": "<<res%21092013<<endl;
	}
}