#include<bits/stdc++.h>
using namespace std;
#define TY int
#define IL inline
#define pb push_back
#define MAXN 105
#define mod (TY)(1e9+7)
#define INF (TY)(1e9)
#define For(i,a,b) for(TY i=(a);i<=(b);++i)
#define FOR(i,a,b) for(TY i=(a);i<(b);++i)
#define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
#define ROF(i,a,b) for(TY i=(a);i>(b);--i)
IL TY qr(){
    TY u=0,v=1;char ch=getchar();
    while(ch>'9'||ch<'0')v=(ch=='-'?-1:1),ch=getchar();
    while(ch>='0'&&ch<='9')u=(u*10)+(ch-'0'),ch=getchar();
    return u*v;
}IL void qw(TY now){
    if(now<0){putchar('-');now=-now;}
    if(!now){putchar('0');return;}
    if(now>=10)qw(now/10);putchar(now%10+'0');
}IL void qw(TY now,char ch){qw(now);putchar(ch);}
IL bool ischar(char u){return u=='Y'||u=='N'||u=='-';}
IL char getc(){
    char u=getchar();
    while(!ischar(u))u=getchar();
    return u;
}IL string qs(){
    string s="";char ch=getchar();
    while(!ischar(ch))ch=getchar();
    while(ischar(ch))s+=ch,ch=getchar();
    return s;
}IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
IL TY Pow(TY a,TY b){
    TY ans=1,base=a;
    while(b){
        if(b&1)ans=ans*base%mod;
        base=base*base%mod;b>>=1;
    }return ans;
}IL TY Mod(TY u){return (u>=mod?u-mod:u);}
TY T,n,d,edge[MAXN][MAXN];
bool vis,ok[MAXN];
IL bool cmp(pair<TY,TY> x,pair<TY,TY> y){return x.first<y.first;}
IL vector<TY> ADD(const vector<TY>&x,const vector<TY>&y){
    vector<TY> lst;
    FOR(i,0,x.size())lst.pb(x[i]);
    FOR(i,0,y.size())lst.pb(y[i]);
    return lst;
}IL vector<TY> Add(const vector<TY>&x,const vector<TY>&y){
    vector<TY> lst;TY idx=0,idy=0;
    while(idx<x.size()||idy<y.size()){
        if(idy==y.size()||(idx!=x.size()&&x[idx]<y[idy])){
            lst.pb(x[idx++]);
        }else lst.pb(y[idy++]);
    }return lst;
}vector<pair<TY,TY> > change(const vector<TY>&now){
    vector<pair<TY,TY> > tmp;
    FOR(i,0,now.size()){
        TY cnt=0;
        FOR(j,0,now.size())if(!edge[now[i]][now[j]]&&i!=j)++cnt;
        tmp.pb({cnt,now[i]});
    }sort(tmp.begin(),tmp.end(),cmp);
    return tmp;
}bool check(const vector<TY>&now,TY op){
    vector<pair<TY,TY> > tmp=change(now);
    TY sum=0;
    bool fir=0,sec=0;
    FOR(i,0,(TY)tmp.size()-1){
        sum+=tmp[i].first;
        if(tmp[i].second==d)fir=1;
        if(fir&&i*(i+1)/2==sum){
            bool ok=1;
            FOR(j,i+1,tmp.size())if(op==-1||edge[op][tmp[j].second])ok=0;
            return ok;
        }
    }return true;
}
vector<TY> solve(vector<TY> now){
    if(now.size()<=1)return now;
    vector<pair<TY,TY> > tmp=change(now);
    vector<TY> fir,sec;
    TY sum=0,lst=0;
    FOR(i,0,(TY)tmp.size()-1){
        sum+=tmp[i].first;
        if(i*(i+1)/2==sum)lst=i+1;
    }FOR(i,0,lst)fir.pb(tmp[i].second);
    FOR(i,lst,tmp.size())sec.pb(tmp[i].second);
    sort(fir.begin(),fir.end());
    TY minn=INF;vector<TY> lstp;
    FOR(i,0,sec.size()){
        vector<TY> ano;
        FOR(j,0,sec.size())if(i!=j)ano.pb(sec[j]);
        if(ok[sec[i]]||check(ano,sec[i])){
            if(sec[i]<minn){
                minn=sec[i];
                lstp=ano;
            }
        }
    }if(minn==INF){vis=0;return fir;}
    tmp=change(lstp);
    if(!ok[minn]){
        memset(ok,0,sizeof(ok));
        For(i,1,n)ok[i]=!edge[minn][i];
    }vector<TY> A,B;
    bool f=0;
    sum=0;
    FOR(i,0,(TY)tmp.size()-1){
        sum+=tmp[i].first;
        if(tmp[i].second==d)f=1;
        A.pb(tmp[i].second);
        if(f&&i*(i+1)/2==sum){
            FOR(j,i+1,tmp.size())B.pb(tmp[j].second);
            break;
        }
    }if(A.size()+B.size()<tmp.size())A.pb(tmp[(TY)tmp.size()-1].second);
    sort(B.begin(),B.end());
    vector<TY> lstans;
    lstans.pb(minn);lstans=ADD(lstans,B);
    return Add(fir,ADD(lstans,solve(A)));
}
int main(){
    T=qr();For(ID,1,T){
        vis=1;memset(ok,0,sizeof(ok));
        n=qr();d=qr()+1;
        For(i,1,n)For(j,1,n)edge[i][j]=(getc()=='Y'?0:1);
        vector<TY> beg,ans;
        For(i,1,n)beg.pb(i);
        if(!check(beg,-1))vis=0;
        ans=solve(beg);
        ws("Case #");qw(ID);ws(": ");
        if(!vis)puts("IMPOSSIBLE");
        else{
            FOR(i,0,ans.size())qw(ans[i]-1,' ');
            putchar('\n');
        }
    }
    return 0;
}