#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5010;
int n,p;
int son[N][2];
int idx;

bool is_end[N];
/*优化：for循环中加入判断条件(!is_end[r]) 
待插入的字符串在向trie树中插入时，若已存在该待插入字符串的前缀，(即插入过程中遇到is_end),则无需继续向下插入
因为以is_end()结尾的字符串ans中已经包含该分支上所有比它长的字符串的答案了，而且is_end()是出口，即便想先插入
也不会递归遍历*/ 
void insert(string str)
{
    int r=0;
    for(int i=0;str[i]&&(!is_end[r]);i++)
    {
        int u=str[i]=='R'?0:1;
        if(!son[r][u])
        son[r][u]=++idx;
        r=son[r][u];        
    }
    is_end[r]=true;
}
/*dfs过程：一直向下遍历，出口为标记的叶节点，返回叶节点的值后通过for循环
遍历与该叶节点同层的节点，通过ans保存该层两个分支的值，返回ans后，通过
for循环保存的上一个状态，即该层的右节点，若此时该层左节点不是叶节点，
则ans为零(因为遍历到该层时执行的是递归调用下一层并未做其他操作，即该状态下的ans为零)
判断右节点是否为叶节点，依次向上返回，通过for循环保存状态*/ 
LL dfs(int u,int k)//U：根节点，K：层数
{
    if(is_end[u])return (1ll<<(n-k));//代表2的(n-k)次幂
    LL ans=0;
    for(int i=0;i<2;i++)//作用：遍历该层的所有情况 
    {
        if(son[u][i])
        {
            ans+=dfs(son[u][i],k+1);//son[u][i]是叶节点则返回值，加上该层右节点，退出for循环，返回ans；
        }
    } 

    return ans;
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {

        cin>>n>>p;

        LL res=0;//记得要重新初始化数据 
        memset(son, 0, sizeof son);
                memset(is_end, false,sizeof is_end);
                idx=0;
        while(p--)
        {
            string str;
            cin>>str;
            insert(str);

        }

        res=(1ll<<n)-dfs(0,0);
        printf("Case #%d: %lld\n", i, res);

    }
    return 0;
}