#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

int N, M;
int A[MAXN+10][MAXN+10];
bool dp[MAXN+10][MAXN+10];
bool P[MAXN+10], Q[MAXN+10];

int main2()
{
    cin >> N >> M;
    for(int i=1; i<=N; i++)
    {
        string S;
        cin >> S;
        for(int j=0; j<M; j++)
        {
            if(S[j]=='.') A[i][j+1]=0;
            else if(S[j]=='#') A[i][j+1]=1;
            else if(S[j]=='O') A[i][j+1]=2;
            else A[i][j+1]=3;
        }
    }

    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
    {
        if(i==1 && j==1) { dp[i][j]=true; continue; }
        dp[i][j]=false;
        if(A[i][j]==1) continue;
        if(i>1) dp[i][j]|=dp[i-1][j];
        if(j>1) dp[i][j]|=dp[i][j-1];
    }

    if(!dp[N][M]) return !(cout << "NIE\n");

    string S;
    for(int i=N, j=M; !(i==1 && j==1); )
    {
        if(i>1 && dp[i-1][j]) S+="D", i--;
        else S+="P", j--;
    }
    reverse(S.begin(), S.end());

    if(A[1][1]==3) P[1]=1;
    int y=1, x=1;
    for(auto c : S)
    {
        if(c=='D')
        {
            y++;
            if(A[y][x]==2 && Q[x]) P[y]=1;
            else if(A[y][x]==3 && !Q[x]) P[y]=1;
        }
        else
        {
            x++;
            if(A[y][x]==2 && P[y]) Q[x]=1;
            else if(A[y][x]==3 && !P[y]) Q[x]=1;
        }
    }

    cout << "TAK\n";
    for(int i=1; i<=N; i++) cout << "NT"[P[i]];
    cout << "\n";
    for(int i=1; i<=M; i++) cout << "NT"[Q[i]];
    cout << "\n";
    cout << S << "\n";

    return 0;
}

void reset()
{
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) dp[i][j]=false;
    for(int i=1; i<=max(N, M); i++) P[i]=Q[i]=false;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int TC;
    cin >> TC;
    while(TC--)
    {
        main2();
        reset();
    }
}