#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; #define int long long #define double long double #define endl "\n" #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) #define lc(x) (x<<1) #define rc(x) (x<<1|1) struct node{ int x,y; bool lr,p; }; int n,m; inline int trs(node A){ if(A.x<0||A.x>n||A.y<0||A.y>m)return 0; return (((A.x-1)*m+A.y)<<1|A.lr)<<1|A.p; } vector<int>g[40030]; int cnt[40300]; int win[40300]; inline node trs(int s){ bool p=s&1; s>>=1; bool lr=s&1; s>>=1; int x=(s-1)/m; s-=(x-1)*m; int y=s; return {x,y,lr,p}; } char mp[110][110]; inline void add(int u,int v){ if(!u||!v)return ; cnt[u]++; g[v].push_back(u); } inline void calc(int x,int y){ memset(win,0,sizeof(win)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=40000;i++) g[i].clear(); for(int x=1;x<=n;x++) for(int y=1;y<=m;y++){ add(trs({x,y,0,0}),trs({x,y,1,0})); add(trs({x,y,0,0}),trs({x,y,1,1})); add(trs({x,y,1,0}),trs({x+1,y,0,0})); add(trs({x,y,1,0}),trs({x-1,y,0,0})); add(trs({x,y,1,1}),trs({x,y+1,0,0})); add(trs({x,y,1,1}),trs({x,y-1,0,0})); } win[trs({x,y,0,0})]=1; queue<int>q; q.push(trs({x,y,0,0})); cnt[trs({x,y,0,0})]=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]=='*') win[trs({i,j,0,0})]=-1,q.push(trs({i,j,0,0})),cnt[trs({i,j,0,0})]=0; while(!q.empty()){ int u=q.front(); q.pop(); for(int v:g[u]) if(win[u]==-1){ if(!cnt[v])continue; win[v]=1; cnt[v]=0; q.push(v); } else if(!(--cnt[v])){ win[v]=-1; q.push(v); } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int t; cin>>t; int id=0; while(t--){ id++; cin>>n>>m; vector<pii>T; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>mp[i][j]; if(mp[i][j]>='a'&&mp[i][j]<='z') T.push_back({i,j}); } vector<string>S; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]>='A'&&mp[i][j]<='Z'){ calc(i,j); for(pii e:T) if(win[trs({p1(e),p2(e),0,0})]!=-1){ string s; s.push_back(mp[p1(e)][p2(e)]); s.push_back(mp[i][j]); S.push_back(s); } } cout<<"Case #"<<id<<" "; if (S.empty()) cout<<"NONE"; else for(string s:S) cout<<s<<" "; cout<<endl; } cout.flush(); return 0; } /* */