#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n;i>=1;i--)
#define mp make_pair
#define pb push_back
int n,m;
char s[2100][2100];
bool f[2100][2100];
int row[2100],col[2100];
pair<int,int> pre[2100][2100];
int main()
{
	int T;
	cin>>T;
	while (T--)
	{
		scanf("%d%d",&n,&m);
		rep(i,n)scanf("%s",s[i]+1);
		rep(i,n)rep(j,m)f[i][j]=0;
		if (f[1][1]!='#')f[1][1]=1;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if (i==1 && j==1)
				if (f[1][1]!='#')f[1][1]=1;
			if (i>1 && f[i-1][j]==1)pre[i][j]=mp(i-1,j),f[i][j]=1;
			if (i>1 && f[i][j-1]==1)pre[i][j]=mp(i,j-1),f[i][j]=1;
			if (s[i][j]=='#')f[i][j]=0;
		}
		if (f[n][m]==0)puts("NIE");
		else
		{
			puts("TAK");
			static vector<char> ans; ans.clear();
			int nowx=n,nowy=m;
			while (nowx!=1 || nowy!=1)
			{
				if (nowx==pre[nowx][nowy].first)ans.pb('P'); else ans.pb('D');
				tie(nowx,nowy)=pre[nowx][nowy];
			}
			reverse(ans.begin(),ans.end());
			nowx=1,nowy=1;
			for(int i=1;i<=n;i++)row[i]=-1;
			for(int i=1;i<=m;i++)col[i]=-1;
			for(auto p:ans)
			{
				if (p=='P')nowy++; else nowx++;
				int f; if (s[nowx][nowy]=='@')f=1;
				if (row[nowx]==1)f^=1;
				if (col[nowy]==1)f^=1;
				if (f)
				{
					if (row[nowx]==-1)row[nowx]=1;
					else col[nowy]=1;
				}
			}
			for(int i=1;i<=n;i++)if (row[i]==1)putchar('T'); else putchar('N'); puts("");
			for(int i=1;i<=m;i++)if (col[i]==1)putchar('T'); else putchar('N'); puts("");
			for(auto p:ans)putchar(p); puts("");
		}
	}
}