#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 2005;
int tt;
int n, m;
bool turn[2][N];
char c[N][N];
bool f[N][N][2][3];
array<int, 5> g[N][N][2][3];
char ans[N << 1];
//0: ÏÂ 1: ÓÒ
//ÊÇ·ñÓж¾Éß 1 2
void dfs(int x, int y, int p, int q, bool C, bool F){
	int val = c[x][y] == '.' ? 0 : (c[x][y] == 'O' ? 1 : 2);
	if (turn[0][x] ^ turn[1][y]) val = (3 - val) % 3;
	if (x == 1 && y == 1){
		if (val == 2)
			turn[ans[1] == 'P'][1] ^= 1;
		return;
	}
	ans[x + y - 2] = "DP"[p];
	if (val == 2 && !C){
		if (p) turn[1][y] ^= 1;
		else turn[0][x] ^= 1;
	}
	if (C && F){
		if (p) turn[0][x] ^= 1;
		else turn[1][y] ^= 1;
	}
	dfs(g[x][y][p][q][0], g[x][y][p][q][1], g[x][y][p][q][2], g[x][y][p][q][3], g[x][y][p][q][2] ^ p, g[x][y][p][q][4]);
}
void solve(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			memset(f[i][j], 0, sizeof(f[i][j]));
			memset(g[i][j], 0, sizeof(g[i][j]));
		}
	for (int i = 1; i <= n; i++)
		turn[0][i] = 0;
	for (int i = 1; i <= m; i++)
		turn[1][i] = 0;
	for (int i = 1; i <= n; i++)
		cin >> (c[i] + 1);
	for (int i : {0, 1})
		f[1][1][i][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			if (c[i][j] == '#') continue;
			int val = c[i][j] == '.' ? 0 : (c[i][j] == 'O' ? 1 : 2);
			//ÏÂÏÂ
			if (i < n)
				for (int k : {0, 1, 2})
					if (f[i][j][0][k]){
						f[i + 1][j][0][k] = 1;
						g[i + 1][j][0][k] = array<int, 5>{i, j, 0, k, 0};
					}
			//ÏÂÓÒ
			if (j < m){
				if (f[i][j][0][0]){
					f[i][j + 1][1][val] = 1;
					g[i][j + 1][1][val] = array<int, 5>{i, j, 0, 0, 0};
				}
				if (f[i][j][0][1]){
					f[i][j + 1][1][val] = 1;
					g[i][j + 1][1][val] = array<int, 5>{i, j, 0, 1, 0};
				}
				if (f[i][j][0][0]){
					f[i][j + 1][1][(3 - val) % 3] = 1;
					g[i][j + 1][1][(3 - val) % 3] = array<int, 5>{i, j, 0, 0, 1};
				}
				if (f[i][j][0][2]){
					f[i][j + 1][1][(3 - val) % 3] = 1;
					g[i][j + 1][1][(3 - val) % 3] = array<int, 5>{i, j, 0, 2, 1};
				}
			}
			//ÓÒÓÒ 
			if (j < m)
				for (int k : {0, 1, 2})
					if (f[i][j][1][k]){
						f[i][j + 1][1][k] = 1;
						g[i][j + 1][1][k] = array<int, 5>{i, j, 1, k, 0};
					}
			//ÓÒÏÂ
			if (i < n){
				if (f[i][j][1][0]){
					f[i + 1][j][0][val] = 1;
					g[i + 1][j][0][val] = array<int, 5>{i, j, 1, 0, 0};
				}
				if (f[i][j][1][1]){
					f[i + 1][j][0][val] = 1;
					g[i + 1][j][0][val] = array<int, 5>{i, j, 1, 1, 0};
				}
				if (f[i][j][1][0]){
					f[i + 1][j][0][(3 - val) % 3] = 1;
					g[i + 1][j][0][(3 - val) % 3] = array<int, 5>{i, j, 1, 0, 1};
				}
				if (f[i][j][1][2]){
					f[i + 1][j][0][(3 - val) % 3] = 1;
					g[i + 1][j][0][(3 - val) % 3] = array<int, 5>{i, j, 1, 2, 1};
				}
			}
		}
	for (int p : {0, 1})
		for (int q : {0, 1, 2})
			if (f[n][m][p][q]){
				cout << "TAK" << endl;
				if (q == 2) turn[p ^ 1][p ? n : m] ^= 1;
				dfs(n, m, p, q, 0, 0);
				for (int i = 1; i <= n; i++)
					cout << "NT"[turn[0][i]];
				cout << endl;
				for (int i = 1; i <= m; i++)
					cout << "NT"[turn[1][i]];
				cout << endl;
				for (int i = 1; i <= n + m - 2; i++)
					cout << ans[i];
				cout << endl;
				return;
			}
	cout << "NIE" << endl;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	cin >> tt;
	while (tt--) solve();
	return 0;
}