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

const int maxn = 2100;

int n,m;
string str[maxn];
int a[maxn][maxn];
int f[maxn][maxn][2][2];
int g[maxn][maxn][2][2],gx[maxn][maxn][2][2],gy[maxn][maxn][2][2];

int main()
{
	ios_base::sync_with_stdio(false);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>str[i];
			str[i]=' '+str[i];
			for(int j=1;j<=m;j++)
			{
				if(str[i][j]=='.') a[i][j]=2;
				else if(str[i][j]=='#') a[i][j]=-1;
				else if(str[i][j]=='O') a[i][j]=0;
				else a[i][j]=1;
			}
		}
		
		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]);
			memset(gx[i][j],0,sizeof gx[i][j]);
			memset(gy[i][j],0,sizeof gy[i][j]);
		}
		for(int x=0;x<2;x++) for(int y=0;y<2;y++) if(a[1][1]==2 || (a[1][1]^x^y)==0 )
		{
			f[1][1][x][y]=1;
		}
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]!=-1)
		{
			int c=a[i][j];
			if(i>1)
			{
				for(int x=0;x<2;x++) for(int y=0;y<2;y++) if(f[i-1][j][x][y])
				{
					for(int nx=0;nx<2;nx++)
					{
						int ny=y;
						if(c==2 || (c^nx^ny)==0 )
						{
							f[i][j][nx][ny]=1;
							g[i][j][nx][ny]=1;
							gx[i][j][nx][ny]=x;
							gy[i][j][nx][ny]=y;
						}
					}
				}
			}
			if(j>1)
			{
				for(int x=0;x<2;x++) for(int y=0;y<2;y++) if(f[i][j-1][x][y])
				{
					for(int ny=0;ny<2;ny++)
					{
						int nx=x;
						if(c==2 || (c^nx^ny)==0 )
						{
							f[i][j][nx][ny]=1;
							g[i][j][nx][ny]=0;
							gx[i][j][nx][ny]=x;
							gy[i][j][nx][ny]=y;
						}
					}
				}
			}
		}
		
		int ax=-1,ay=-1;
		for(int x=0;x<2;x++) for(int y=0;y<2;y++) if(f[n][m][x][y])
		{
			ax=x;
			ay=y;
		}
		
		if(ax!=-1)
		{
			cout<<"TAK\n";
			vector<int>ans;
			vector<int>row(n+5),col(m+5);
			{
				int i=n,j=m;
				row[n]=ax;
				col[m]=ay;
				while(i!=1||j!=1)
				{
					int nx=gx[i][j][ax][ay], ny=gy[i][j][ax][ay];
					int dir=g[i][j][ax][ay];
					ans.push_back(dir);
					if(dir==0) j--;
					else i--;
					ax=nx, ay=ny;
					row[i]=ax;
					col[j]=ay;
				}
			}
			for(int	i=1;i<=n;i++) cout<<(row[i]?'T':'N');
			cout<<'\n';
			for(int j=1;j<=m;j++) cout<<(col[j]?'T':'N');
			cout<<'\n';
			for(int i=n+m-3;i>=0;i--) cout<<(ans[i]?'D':'P');
			cout<<'\n';
		}
		else
		{
			cout<<"NIE\n";
		}
	}
	
	return 0;
}