#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
struct node{
    int x,y;
    string stp;
};
string mp[2050];
int vis[2050][2050],nowr[2050],nowc[2050];
int dx[5]={1,0},dy[5]={0,1};
void solve(){
    ms(vis,0);ms(nowr,0);ms(nowc,0);
    int n,m,flg=0;cin>>n>>m;
    string ans;
    fn(i,0,n-1)cin>>mp[i];
    queue<node>q;vis[0][0]=1;
    q.push({0,0,""});
    while(!q.empty()){
        node now=q.front();q.pop();
        int nx=now.x,ny=now.y;
        string stp=now.stp;
        if(nx<0||ny<0||mp[nx][ny]=='#'||nx>n-1||ny>m-1||vis[nx][ny])continue;vis[nx][ny]=1;
        if(nx==n-1&&ny==m-1){
            ans=stp,flg=1;
            break;
        }
        fn(i,0,1){
            int tx=nx+dx[i],ty=ny+dy[i];
            if(tx<0||ty<0||mp[tx][ty]=='#'||vis[tx][ty]||tx>n-1||ty>m-1)continue;vis[tx][ty]=1;
            if(!i)stp+='D';
            else stp+='P';
            q.push({tx,ty,stp});
        }
    }
    if(!flg){cout<<"NIE\n";return;}
    int nx=0,ny=0;
    string nr="",nc="";
    if(mp[0][0]=='@'){nr+='T',nc+='N';nowr[0]^=1;}
    else nr+='N',nc+='N';
    fn(i,0,n+m-3){
        if(ans[i]=='D')nx++;
        else ny++;
        if((mp[nx][ny]=='@'&&(!(nowr[nx]^nowc[ny])))||(mp[nx][ny]=='O'&&(nowr[nx]^nowc[ny]))){
            if(ans[i]=='D')nr+='T',nowr[nx]^=1;
            else nc+='T',nowc[ny]^=1;
        }
        else {
            if(ans[i]=='D')nr+='N';
            else nc+='N';
        }
    }
    cout<<"TAK\n"<<nr<<"\n"<<nc<<"\n"<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}