#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

string mp[2005];
int dp[2005][2005][4], tr[2005][2005][4];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> mp[i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            fill_n(dp[i][j], 4, 0);
    if (mp[0][0] == '.') fill_n(dp[0][0], 4, 1);
    else if (mp[0][0] == 'O') dp[0][0][0] = dp[0][0][3] = 1;
    else if (mp[0][0] == '@') dp[0][0][1] = dp[0][0][2] = 1;
    else assert(0);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < 4; ++k) {
                if (!dp[i][j][k]) continue;
                if (i + 1 < n && mp[i + 1][j] != '#') {
                    if (mp[i + 1][j] == '.') {  
                        dp[i + 1][j][k & 1] = dp[i + 1][j][(k & 1) | 2] = 1;
                        tr[i + 1][j][k & 1] = 0 + (k << 8);
                        tr[i + 1][j][(k & 1) | 2] = 2 + (k << 8);
                    }
                    else if (mp[i + 1][j] == 'O') {
                        if (k & 1) {
                            dp[i + 1][j][3] = 1;
                            tr[i + 1][j][3] = 2 + (k << 8);
                        }
                        else {
                            dp[i + 1][j][0] = 1;
                            tr[i + 1][j][0] = 0 + (k << 8);
                        }
                    }
                    else {
                        if (k & 1) {
                            dp[i + 1][j][1] = 1;
                            tr[i + 1][j][1] = 0 + (k << 8);
                        }
                        else {
                            dp[i + 1][j][2] = 1;
                            tr[i + 1][j][2] = 2 + (k << 8);
                        }
                    }
                }
                if (j + 1 < m && mp[i][j + 1] != '#') {
                    if (mp[i][j + 1] == '.') {
                        dp[i][j + 1][k & 2] = dp[i][j + 1][(k & 2) | 1] = 1;
                        tr[i][j + 1][k & 2] = 1 + (k << 8);
                        tr[i][j + 1][(k & 2) | 1] = 3 + (k << 8);
                    }
                    else if (mp[i][j + 1] == 'O') {
                        if (k & 2) {
                            dp[i][j + 1][3] = 1;
                            tr[i][j + 1][3] = 3 + (k << 8);
                        }
                        else {
                            dp[i][j + 1][0] = 1;
                            tr[i][j + 1][0] = 1 + (k << 8);
                        }
                    }
                    else {
                        if (k & 2) {
                            dp[i][j + 1][2] = 1;
                            tr[i][j + 1][2] = 1 + (k << 8);
                        }
                        else {
                            dp[i][j + 1][1] = 1;
                            tr[i][j + 1][1] = 3 + (k << 8);
                        }
                    }
                }
            }
        }

    int flag = -1;
    for (int i = 0; i < 4; ++i)
        if (dp[n - 1][m - 1][i])
            flag = i;
    if (flag == -1) cout << "NIE\n";
    else {
        cout << "TAK\n";
        string row(n, 'N'), col(m, 'N'), ans;
        int x = n - 1, y = m - 1;
        while (x || y) {
            if (tr[x][y][flag] & 1) {
                if (tr[x][y][flag] & 2) col[y] = 'T';
                ans.pb('P'), flag = tr[x][y][flag] >> 8, --y;
            }
            else {
                if (tr[x][y][flag] & 2) row[x] = 'T';
                ans.pb('D'), flag = tr[x][y][flag] >> 8, --x;
            }
        }
        if (flag & 1) col[0] = 'T';
        if (flag & 2) row[0] = 'T';
        reverse(ALL(ans));
        cout << row << "\n";
        cout << col << "\n";
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}