#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define INF 1e9
#define INFl 1e18
#define all(x) x.begin(), x.end()
#define sajz(x) (int)x.size()
#define pb push_back
#define s second
#define f first
#define yes puts("YES")
#define no puts("NO")
#define erase_duplicates(x) {sort(all(x));(x).resize(distance((x).begin(), unique(all(x))));}
using namespace std;
//using namespace __gnu_pbds;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int ll

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;
typedef multiset<int> msi;
typedef long double ld;
//typedef cc_hash_table<int, int, hash<int>> ht;

const int N = 2005;

int a[N][N];
pii par[N][N];
bool odw[N][N];
char r[N][N];
int n, m;

pii prawo = {0, 1};
pii dol = {1, 0};

bool good(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m && a[x][y] != 3 && !odw[x][y];
}

void test_case() {
	cin >> n >> m;

	for (int i = 0; i < n; i ++) 
		for (int j = 0; j < m; j ++) {
			odw[i][j] = false;
			char z;
			cin >> z;
			if (z == 'O') a[i][j] = 0;
			if (z == '@') a[i][j] = 1;
			if (z == '.') a[i][j] = 2;
			if (z == '#') a[i][j] = 3;
		}

	par[0][0] = {0, 0};
	queue<pii> q;
	q.push({0, 0});
	odw[0][0] = true;

	while (!q.empty()) {
		pii v = q.front();
		q.pop();

		if (good(v.f + prawo.f, v.s + prawo.s)) {
			odw[v.f+prawo.f][v.s+prawo.s] = true;
			par[v.f+prawo.f][v.s+prawo.s] = v;
			r[v.f+prawo.f][v.s+prawo.s] = 'P';
			q.push({v.f+prawo.f, v.s+prawo.s});
		}

		if (good(v.f + dol.f, v.s + dol.s)) {
			odw[v.f+dol.f][v.s+dol.s] = true;
			par[v.f+dol.f][v.s+dol.s] = v;
			r[v.f+dol.f][v.s+dol.s] = 'D';
			q.push({v.f+dol.f, v.s+dol.s});
		}
	}

	if (!odw[n-1][m-1]) {
		cout << "NIE\n";
		return;
	}

	vector<char> ans;
	
	pii cur = {n-1, m-1};
	while (cur != make_pair(0LL, 0LL)) {
		ans.pb(r[cur.f][cur.s]);
		cur = par[cur.f][cur.s];
	}

	reverse(all(ans));

	//debug(ans);

	cur = {0, 0};
	vi row(n), col(m);
	for (int i = 0; i <= sajz(ans); i ++) {
		//debug(cur);
		if (a[cur.f][cur.s] != 2 && (a[cur.f][cur.s]^row[cur.f]^col[cur.s]) == 1) {
			if (ans[max(0LL, i-1)] == 'D') {
				row[cur.f] = 1;
			} else {
				col[cur.s] = 1;
			}
		}

		if (i < sajz(ans)) {
			if (ans[i] == 'P') cur.s ++;
			else cur.f ++;
		}
	}

	cout << "TAK\n";
	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';

	for (auto it : ans) cout << it;
	cout << '\n';
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--) test_case();

	return 0;
}