#include <iostream>

using namespace std;

const int mod = 21092013;

typedef long long LL;

int fa[100100],lson[100100],rson[100100];
int T;
char ch[100100];

int main(){
	scanf("%d",&T);
	for (int ti=1;ti<=T;ti++){
		scanf("%s",ch);
		int l = strlen(ch);
		
		memset(fa,0,sizeof(fa));
		memset(lson,0,sizeof(lson));
		memset(rson,0,sizeof(rson));
		
		int now = 0;
		int tot = 0;
		for (int i=0;i<l;i++){
			if (ch[i]=='L'){
				if (lson[now]!=0) now=lson[now];
					else {
						++tot;
						lson[now]=tot;
						fa[tot]=now;
						now = tot;
					}
			}
			if (ch[i]=='R'){
				if (rson[now]!=0) now=rson[now];
					else {
						++tot;
						rson[now]=tot;
						fa[tot]=now;
						now=tot;
					}
			}
			if (ch[i]=='U'){
				now = fa[now];
			}
		}

		scanf("%s",ch);
		l = strlen(ch);

		int root=now;
		LL ans = 1;
		LL x,y,z;
		x=y=0;z=1;
		for (int i=0;i<l;i++){
			if (ch[i]=='L'){
				ans += x + z;
				ans %= mod;
				y = y+z;
				z = x+z;
				x = 0;
				y %= mod;
				x %= mod;
				z %= mod;
			}
			if (ch[i]=='R'){
				ans += y + z;
				ans %= mod;
				x = x+z;
				z = y+z;
				y = 0;
				x %= mod;
				y %= mod;
				z %= mod;
			}
			if (ch[i]=='U'){
				if (root>0){
					ans++;
					if (lson[fa[root]]==root) y++;
					if (rson[fa[root]]==root) x++;
				}
				root = fa[root];
				x %= mod;
				y %= mod;
			}
		}
		
		printf("Case %d: %lld\n",ti,ans);
		
	}
	return 0;
}