#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define pii pair<int,int>
#define mk make_pair
#define ft first
#define se second
#define pb push_back
#define db double
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define inf 1e18
using namespace std;
#define LOCAL
namespace IO{
    #ifndef LOCAL
        #define SIZE 30000
        char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
        #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
        #define flush() (fwrite(p3=out,1,SIZE,stdout))
        #define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
        class Flush{public:~Flush(){fwrite(out,1,p3-out,stdout);}}_;
    #endif
    template<typename type>
    inline void read(type &x){
        x=0;bool flag=0;char ch=getchar();
        while(ch<'0'||ch>'9') flag^=ch=='-',ch=getchar();
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        flag?x=-x:0;
    }
    template<typename type>
    inline void write(type x,char ch=0){
        x<0?x=-x,putchar('-'):0;static short Stack[50],top=0;
        do Stack[++top]=x%10,x/=10;while(x);
        while(top) putchar(Stack[top--]|48);
        if(ch) putchar(ch);
    }
}
using namespace IO;
#define M 2005
int n,m,d,dx[2]={-1,0},dy[2]={0,-1};
bool vis[M][M];
char mp[M][M],row[M],col[M],opr[M<<1];
bool check(){
    queue<pii> q;
    vis[n][m]=1,q.push(mk(n,m));
    while(!q.empty()){
        pii u=q.front();q.pop();
        for(int i=0;i<2;i++){
            int nx=u.ft+dx[i],ny=u.se+dy[i];
            if(nx>0&&nx<=n&&nx>0&&ny<=m&&mp[nx][ny]!='#'&&!vis[nx][ny]){
                if(nx==1&&ny==1) return 1;
                vis[nx][ny]=1;q.push(mk(nx,ny));
            }
        }
    }
    return 0;
}
void flipRow(int rr){
    if(row[rr]=='N') row[rr]='T';
    else row[rr]='N';
    for(int i=1;i<=m;i++){
        if(mp[rr][i]=='O') mp[rr][i]='@';
        else if(mp[rr][i]=='@') mp[rr][i]='O';
    }
}
void flipCol(int cc){
    if(col[cc]=='N') col[cc]='T';
    else col[cc]='N';
    for(int i=1;i<=n;i++){
        if(mp[i][cc]=='O') mp[i][cc]='@';
        else if(mp[i][cc]=='@') mp[i][cc]='O';
    }
}
void dfs(int x,int y){
    if(x==n&&y==m) return;
    if(x==n){
        if(mp[x][y+1]=='@') flipCol(y+1);
        opr[++d]='P';
        dfs(x,y+1);
        return;
    }
    if(y==m){
        if(mp[x+1][y]=='@') flipRow(x+1);
        opr[++d]='D';
        dfs(x+1,y);
        return;
    }
    if(vis[x][y+1]){
        if(mp[x][y+1]=='@') flipCol(y+1);
        opr[++d]='P';
        dfs(x,y+1);
        return;
    }
    if(vis[x+1][y]){
        if(mp[x+1][y]=='@') flipRow(x+1);
        opr[++d]='D';
        dfs(x+1,y);
        return;
    }
}
void solve(){
    read(n),read(m),d=0;
    for(int i=1;i<=n;i++) row[i]='N';
    for(int i=1;i<=m;i++) col[i]='N';
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
        for(int j=1;j<=m;j++) vis[i][j]=0;
    }
    if(!check()) puts("NIE");
    else{
        puts("TAK");
        dfs(1,1);
        printf("%s\n%s\n%s\n",row+1,col+1,opr+1);
    }
}
int main(){
    int T;read(T);
    while(T--) solve();
    return 0;
}