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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 2137
#endif

const int N = 2020;
int n, m;
string g[N];
array<int, 3> go[N][N][4];

bool ok(int x, int y, int msk) {
  if (g[x][y] == '.') {
    return true;
  }
  if (g[x][y] == '#') {
    return false;
  }
  return (g[x][y] == 'O') ^ __builtin_parity(msk);
}

void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> g[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < 4; k++) {
        go[i][j][k] = {-1, -1, -1};
      }
    }
  }
  queue<array<int, 3>> q;
  for (int i = 0; i < 4; i++) {
    if (ok(0, 0, i)) {
      q.push({0, 0, i});
    }
  }
  while (!q.empty()) {
    auto [i, j, k] = q.front();
    q.pop();
    for (int it = 0; it < 2; it++) {
      if (i + 1 < n) {
        int kk = (k & 2) | it;
        if (ok(i + 1, j, kk) && go[i + 1][j][kk][0] == -1) {
          go[i + 1][j][kk] = {i, j, k};
          q.push({i + 1, j, kk});
        }
      }
      if (j + 1 < m) {
        int kk = (k & 1) | (it << 1);
        if (ok(i, j + 1, kk) && go[i][j + 1][kk][0] == -1) {
          go[i][j + 1][kk] = {i, j, k};
          q.push({i, j + 1, kk});
        }
      }
    }
  }
  int k = 0;
  for (int i = 0; i < 4; i++) {
    if (go[n - 1][m - 1][i][0] != -1) {
      k = i;
    }
  }
  if (go[n - 1][m - 1][k][0] == -1) {
    cout << "NIE\n";
    return;
  }
  int i = n - 1;
  int j = m - 1;
  string x(n, 'N'), y(m, 'N'), z;
  while (i != -1) {
    debug(i, j, k);
    auto [p, q, r] = go[i][j][k];
    if (k & 1) {
      x[i] = 'T';
    }
    if (k & 2) {
      y[j] = 'T';
    }
    if (i > 0 || j > 0) {
      z.push_back(i != p ? 'D' : 'P');
    }
    i = p;
    j = q;
    k = r;
  }
  reverse(z.begin(), z.end());
  cout << "TAK\n" << x << '\n' << y << '\n' << z << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}