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

#define cs const
#define pb push_back

cs int N = 2e3 + 50, M = N * N * 4; 
int T; 
int n, m; 
char mp[N][N];

vector <int> e[M];
int vis[M];


int id(int i, int j, int o, int e) {
    if(mp[i][j] == '#') return 0; 
    int z = (mp[i][j] == '@') ^ o ^ e;
    if(z) return 0; 
    return 4 * ((i - 1) * m + j - 1) + o * 2 + e; 
}
int A(int x) {
    x >>= 2; 
    x = x / m;
    return x + 1; 
}
int B(int x) {
    x >>= 2;
    x = x % m; 
    return x + 1;
}
int O(int x) {
    return x >> 1 & 1; 
}
int E(int x) {
    return x & 1; 
}


void clear(){
    int nn = 4 * n * m + 5; 
    for(int i = 0; i <= nn; i++) e[i].clear(), vis[i] = 0; 
}

void add(int a, int b, int c, int d, int e, int f, int g, int h) {
    int x = id(a, b, c, d), y = id(e, f, g, h);
    if(x && y) :: e[x].pb(y);
}
void con(int a, int b, int c, int d, int f) {
    if(a == c) {
        for(int l = 0; l < 2; l++) 
            for(int r = 0; r < 2; r++)
                add(a, b, f, l, c, d, f, r);
        return;
    }
    // cerr << a << ' ' << b << ' ' << c << ' ' << d << endl;
    assert(b == d);
    for(int l = 0; l < 2; l++) 
        for(int r = 0; r < 2; r++)
            add(a, b, l, f, c, d, r, f);
}
void conn(int a, int b, int c, int d) {
    con(a, b, c, d, 0);
    con(a, b, c, d, 1);
}

int ans1[N], ans2[N];
string ans3; 
void work(int x) {
    int y = vis[x];

    if(O(x)) ans1[A(x)] = 1;
    else ans1[A(x)] = 0;
    if(E(x)) ans2[B(x)] = 1;
    else ans2[B(x)] = 0; 

    if(y == 0) return;
    if(A(y) == A(x)) ans3 += 'P';
    else assert(B(y) == B(x)), ans3 += 'D';

    // cout << " PATH " << A(x) << ' ' << B(x) << ' ' << O(x) << ' ' << E(x) << endl;
    work(y);
}

void Main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%s", mp[i] + 1); 
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(i > 1) conn(i - 1, j, i, j);
            if(j > 1) conn(i, j - 1, i, j);
        }
    }
    
    queue <int> q; 
    for(int l = 0; l < 2; l++) 
        for(int r = 0; r < 2; r++)
            q.push(id(1, 1, l, r));
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int v : e[x]) if(!vis[v]) {
            vis[v] = x; 
            q.push(v);
        }
    }
    for(int i = 0; i <= max(n, m); i++) ans1[i] = ans2[i] = -1; 
    ans3.clear();
    for(int l = 0; l < 2; l++) 
        for(int r = 0; r < 2; r++) 
            if(vis[id(n, m, l, r)]) {
                work(id(n, m, l, r));
                reverse(ans3.begin(), ans3.end());
                cout << "TAK\n";
                for(int i = 1; i <= n; i++) cout << (ans1[i] == 1 ? "T" : "N");
                cout << '\n';
                for(int i = 1; i <= m; i++) cout << (ans2[i] == 1 ? "T" : "N");
                cout << '\n';
                cout << ans3 << '\n';
                return;
            }
    cout << "NIE\n";
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif 
    cin >> T; 
    while(T--) Main(), clear();
    return 0; 
}