#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int N=2005;
char mp[N][N];
int n,m,k,f[N][N][2][2];
vector<char>ans1,ans2,ans3;
void getans(int x,int y,int u,int v){
    if(x==1&&y==1) return ;
    //printf("#%d %d %d %d\n",x,y,u,v);
    if(f[x][y][u][v]==1){
        rep(i,0,1){
            if(f[x][y-1][i][v]){
                getans(x,y-1,i,v);
                ans2.push_back(i?'T':'N');
                ans3.push_back('P');
                break;
            }
        }
    }else{
        rep(i,0,1){
            if(f[x-1][y][u][i]){
                getans(x-1,y,u,i);
                ans1.push_back(i?'T':'N');
                ans3.push_back('D');
                break;
            }
        }
    }
}
void solve(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        scanf("%s",mp[i]+1);
    }
    if(mp[1][1]=='.'){
        f[1][1][0][0] = 1;
        f[1][1][1][1] = 1;
    }else{
        f[1][1][0][1] = 1;
        f[1][1][1][0] = 1;
    }
    rep(i,1,n){
        rep(j,1,m){
            if(j<m&&mp[i][j+1]!='#'){//1 => j+1 2=>i+1
                if(mp[i][j+1]=='.'){
                    if(f[i][j][0][0]||f[i][j][1][0])
                        f[i][j+1][0][0] = 1,
                        f[i][j+1][1][0] = 1;
                    if(f[i][j][0][1]||f[i][j][1][1])
                        f[i][j+1][0][1] = 1,
                        f[i][j+1][1][1] = 1;
                }else{
                    if(mp[i][j+1]=='O'){
                        if(f[i][j][0][0]||f[i][j][1][0])
                            f[i][j+1][0][0] = 1;
                        if(f[i][j][0][1]||f[i][j][1][1])
                            f[i][j+1][1][1] = 1;
                    }else{
                        if(f[i][j][0][0]||f[i][j][1][0])
                            f[i][j+1][1][0] = 1;
                        if(f[i][j][0][1]||f[i][j][1][1])
                            f[i][j+1][0][1] = 1;
                    }
                }
            }

            if(i<n&&mp[i+1][j]!='#'){
                if(mp[i+1][j]=='.'){
                    if(f[i][j][0][0]||f[i][j][0][1])
                        f[i+1][j][0][0] = 2,
                        f[i+1][j][0][1] = 2;
                    if(f[i][j][1][0]||f[i][j][1][1])
                        f[i+1][j][1][0] = 2,
                        f[i+1][j][1][1] = 2;
                }else{
                    if(mp[i+1][j]=='O'){
                        if(f[i][j][0][0]||f[i][j][0][1])
                            f[i+1][j][0][0] = 2;
                        if(f[i][j][1][0]||f[i][j][1][1])
                            f[i+1][j][1][1] = 2;
                    }else{
                        if(f[i][j][0][0]||f[i][j][0][1])
                            f[i+1][j][0][1] = 2;
                        if(f[i][j][1][0]||f[i][j][1][1])
                            f[i+1][j][1][0] = 2;
                    }
                }
            }

        }
    }
    rep(i,0,1) rep(j,0,1) if(f[n][m][i][j]){
        puts("TAK");
        getans(n,m,i,j);
        ans2.push_back(i?'T':'N');
        ans1.push_back(j?'T':'N');
        for(auto v:ans1) putchar(v); puts("");
        for(auto v:ans2) putchar(v); puts("");
        for(auto v:ans3) putchar(v); puts("");
        return ;
    }
    puts("NIE");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}