#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

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

#define ll long long
#define ld long double

const int N = 2000 + 5, mod = 1e9 + 7;

int n, m, dp[N][N][2][3];
char row[N], col[N];
string s[N], ans;

int getState(int i, int j) {
    assert(s[i][j] != '#');
    return s[i][j] == 'O' ? 1 : (s[i][j] == '.' ? 0 : 2);
}

int solve(int i, int j, bool row, int state) {
    if (i == n - 1 && j == m - 1) {
        return 1;
    }
    auto &ret = dp[i][j][row][state];
    if (~ret) {
        return ret;
    }
    ret = 0;
    if (j + 1 < m) {
        auto nxt = s[i][j + 1];
        if (nxt != '#') {
            auto nxt_state = getState(i, j + 1);
            auto can = nxt == '.' || !row || !state || state == nxt_state;
            if (can) {
                ret |= solve(i, j + 1, 1, nxt_state != 0 ? nxt_state : (row ? state : 0));
            }
        }
    }
    if (i + 1 < n) {
        auto nxt = s[i + 1][j];
        if (nxt != '#') {
            auto nxt_state = getState(i + 1, j);
            auto can = nxt == '.' || row || !state || state == nxt_state;
            if (can) {
                ret |= solve(i + 1, j, 0, nxt_state != 0 ? nxt_state : (!row ? state : 0));
            }
        }
    }
    return ret;
}

void build(int i, int j, bool is_row, int state) {
    if (is_row) {
        if (state == 2) {
            row[i] = 'T';
        } else if (state == 1) {
            row[i] = 'N';
        }
    } else {
        if (state == 2) {
            col[j] = 'T';
        } else if (state == 1) {
            col[j] = 'N';
        }
    }
    if (i == n - 1 && j == m - 1) {
        return;
    }
    if (j + 1 < m) {
        auto nxt = s[i][j + 1];
        if (nxt != '#') {
            auto nxt_state = getState(i, j + 1);
            auto can = nxt == '.' || !is_row || !state || state == nxt_state;
            if (can) {
                if (solve(i, j + 1, 1, nxt_state != 0 ? nxt_state : (is_row ? state : 0))) {
                    ans += 'P';
                    build(i, j + 1, 1,nxt_state != 0 ? nxt_state : (is_row ? state : 0));
                    return;
                }
            }
        }
    }
    ans += 'D';
    auto nxt_state = getState(i + 1, j);
    build(i + 1, j, 0, nxt_state != 0 ? nxt_state : (!is_row ? state : 0));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string yes = "TAK", no = "NIE";

    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i) {
            cin >> s[i];
        }
        memset(dp, -1, n * sizeof (dp[0]));
        memset(row, 0, sizeof (row));
        memset(col, 0, sizeof (col));
        ans.clear();
        if (solve(0, 0, 0, 0)) {
            cout << yes << '\n';
            build(0, 0, 0, 0);
            for (int i = 0; i < n; ++i) {
                cout << (row[i] ? 'T' : 'N');
            }
            cout << '\n';
            for (int i = 0; i < m; ++i) {
                cout << (col[i] ? 'T' : 'N');
            }
            cout << '\n';
            cout << ans << '\n';
        } else {
            cout << no << '\n';
        }
    }

    return 0;
}