//#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int N=;

 const int mod=;

 const int NN=;

 char g[N][N];

 LL ans;

 int cur, n, m, ex, ey, tx, ty;

 struct Hash_Map

 {

     int head[mod];      //桶指针

     int next[NN];        //记录链的信息

     LL  status[NN];      //状态

     LL  value[NN];       //状态对应的DP值。

     int size;

     void clear()    //清除哈希表中的状态

     {

         memset(head, -, sizeof(head));

         size = ;

     }

     void insert(LL st, LL val)  //插入状态st的值为val

     {

         int h = st%mod;

         for(int i=head[h]; ~i; i=next[i])

             if(status[i] == st) //这个状态已经存在，累加进去。

             {

                 value[i] += val;

                 return ;

             }

         status[size]= st;           //找不到状态st，则插入st。

         value[size] = val;

         next[size] = head[h] ;      //新插入的元素在队头

         head[h] = size++;

     }

 }hashmap[];

 inline int getbit(LL s,int pos)   //取出状态s的第pos个插头

 {

     return (s>>*pos)&;

 }

 inline int setbit(LL s,int pos,int bit)   //将状态s的第pos个插头设置为bit

 {

     if(s&(<<*pos ))     s^=<<(*pos);

     if(s&(<<(*pos+)))  s^=<<(*pos+);

     return (s|(bit<<*pos));

 }

 int Fr(LL s,int pos,int bit)   //寻找状态s的第pos个插头对应的右括号。

 {

     int cnt=;

     for(pos+=; pos<m; pos++)

     {

         if(getbit(s, pos)==-bit)   cnt++;

         if(getbit(s, pos)==bit)     cnt--;

         if(cnt==-)         return setbit(s, pos, -bit);

     }

 }

 int Fl(LL s,int pos,int bit)   //寻找状态s的第pos个插头对应的左括号。

 {

     int cnt=;

     for(pos--; pos>=; pos--)

     {

         if(getbit(s, pos)==-bit)  cnt++;

         if(getbit(s, pos)==bit)    cnt--;

         if( cnt==-)    return setbit(s, pos, -bit);

     }

 }

 void DP(int i,int j)    //非障碍空格

 {

     LL t;

     for(int k=; k<hashmap[cur^].size; k++)

     {

         LL s=hashmap[cur^].status[k];

         LL v=hashmap[cur^].value[k];

         int R=getbit(s,j), D=getbit(s,j+);

         if(g[i][j]=='X')    //障碍格子

         {

             if( R== && D== )    hashmap[cur].insert(s, v);

             continue ;

         }

         if(R && D)  //两个括号

         {

             t=(setbit(s,j,)&setbit(s,j+,));

             if(R==D)    //同个方向的括号

             {

                 if(R==)    t=Fr(t, j, );  //要改

                 else        t=Fl(t, j, );

                 hashmap[cur].insert(t, v);

             }

             else if( R== && D== )        //不同的连通分量

                 hashmap[cur].insert(t, v);

             else if(t== && ( i>ex || (i==ex && j>=ey)))    //注意点！

                 ans+=v;

         }

         else if(R || D)     //仅1个括号

         {

             if(R)

             {

                 if(i+<n && g[i+][j]!='X')   hashmap[cur].insert(s, v);

                 if(j+<m && g[i][j+]!='x')   hashmap[cur].insert(setbit(setbit(s,j,), j+, R), v);

             }

             else

             {

                 if(j+<m && g[i][j+]!='X')   hashmap[cur].insert(s, v);

                 if(i+<n && g[i+][j]!='X')   hashmap[cur].insert(setbit(setbit(s,j+,), j, D), v);

             }

         }

         else                //无括号

         {

             if( g[i][j+]!='X' && g[i+][j]!='X' && j+<m && i+<n )    //新括号

                 hashmap[cur].insert( setbit(s,j,)|setbit(s,j+,), v);

             if( g[i][j]=='*' )      //此点可不走

                 hashmap[cur].insert( s, v);

         }

     }

 }

 void cal()

 {

     for(int i=; i<n; i++)

     {

         cur^=;

         hashmap[cur].clear();

         for(int j=; j<hashmap[cur^].size; j++)    //新行，需要左移一下状态。

             hashmap[cur].insert( hashmap[cur^].status[j]<<, hashmap[cur^].value[j] );

         for(int j=; j<m; j++)

         {

             cur^=;

             hashmap[cur].clear();

             DP(i,j);

             if(i==tx && j==ty)    return ;  //最后的有效点

         }

     }

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int t, Case=;

     cin>>t;

     while(t--)

     {

         tx=ty=ex=ey=-;

         ans=cur=;

         memset(g, 'X', sizeof(g));

         scanf("%d%d",&n,&m);

         for(int i=; i<n; i++)      //输入矩阵

         {

             for(int j=; j<m; j++)

             {

                 char c=getchar();

                 if(c=='X'||c=='*'||c=='O')

                 {

                     g[i][j]=c;

                     if( c=='O' )    ex=i,ey=j;  //必走格

                     if( c!='X' )    tx=i,ty=j;  //终点格

                 }

                 else    j--;

             }

         }

         hashmap[cur].clear();

         hashmap[cur].insert(, );  //初始状态

         cal();

         cout<<"Case "<<++Case<<": "<<ans<<endl;

     }

     return ;

 }