#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 2010;
int n, m, vis[N][N], pre[N][N];
string str[N];
void solve() {
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> str[i];
		str[i] = "#" + str[i];
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			vis[i][j] = 0;
		}
	}
	vis[1][1] = 1;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			if(str[i][j] == '#') {
				vis[i][j] = 0;
			}
			if(vis[i][j]) {
				vis[i + 1][j] = 1;
				pre[i + 1][j] = 0;
				vis[i][j + 1] = 1;
				pre[i][j + 1] = 1;
			}
		}
	}
	if(vis[n][m]){
		cout << "TAK\n";
		string s(n, 'N'), t(m, 'N'), p;
		auto row = [&] (int x) {
			s[x - 1] = 'T';
			for(int i = 1; i <= m; i ++) {
				if(str[x][i] == '@') str[x][i] = 'O';
				else if(str[x][i] == 'O') str[x][i] = '@';
			}
		};
		auto col = [&] (int x) {	
			t[x - 1] = 'T';
			for(int i = 1; i <= n; i ++) {
				if(str[i][x] == '@') str[i][x] = 'O';
				else if(str[i][x] == 'O') str[i][x] = '@';
			}
		};
		function<void(int, int)> dfs = [&] (int x, int y) {
			if(x == 1 && y == 1) {
				if(str[x][y] == '@') row(1);
				return ;
			}
			if(pre[x][y]) {
				dfs(x,  y - 1);
				p += "P";
				if(str[x][y] == '@') col(y);
			}
			else {
				dfs(x - 1, y);
				p += "D";
				if(str[x][y] == '@') row(x);
			}
		};
		dfs(n, m);
		cout << s << '\n' << t << '\n' << p << '\n';
	} else {
		cout << "NIE\n";
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	for(cin >> T; T; T --) {
		solve();
	}
 	return 0;
}