可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。 
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。

Input输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。Output如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。Sample Input

1
5 5 14
S*#*.
.#…
…..
****.
…#.

..*.P
#.*..
***..
…*.
*.#..

Sample Output

YES

#include
#include
#include
#include
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const LL maxn = 13;
const int inf = 1<<30;//每一次乘以2 int N, M, T; int vis[4][maxn][maxn]; //vis为到达该点的最短时间, -1为不可达, inf为未走过 char mp[4][maxn][maxn]; //地图[层数][x][y]; int f[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //前后左右, 上下 bool check(int cx, int cy) { if(cx>0&&cx<=N&&cy>0&&cy<=M) return 1; else return 0; } bool Dfs(int x, int y, int z, int t) { if(mp[z][x][y]=='P') return true; if(t==T) return false; int cx, cy, cz; for(int i = 0; i < 4; i++) { cx = x+f[i][0], cy = y+f[i][1], cz = z; if(check(cx, cy) && vis[cz][cx][cy]>t+1)
{
if(mp[cz][cx][cy]=='.' || mp[cz][cx][cy]=='P')
{
vis[cz][cx][cy] = t+1; //改变时间戳
if(Dfs(cx, cy, cz, t+1)) return true;
}
else if(mp[cz][cx][cy]=='#') //碰见传送门必传送
{
vis[cz][cx][cy] = t+1; //改变时间戳
cz = (z==1)?2:1;
if(mp[cz][cx][cy]=='#' || mp[cz][cx][cy]=='*')//*和#都不能通过
{
vis[cz][cx][cy] = vis[z][cx][cy] = -1; //设置为不可达
continue;
}
vis[cz][cx][cy] = t+1;
if(Dfs(cx, cy, cz, t+1)) return true; //不花费时间
}
}
}
return false;
}
int main()
{
int C;
cin >> C;
while(C--)
{
ms(vis, 0); ms(mp, 0);
cin >> N >> M >> T;
for(int k = 1; k <= 2; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) { cin >> mp[k][i][j];
vis[k][i][j] = inf; //初始化
}
//开始深搜
vis[1][1][1] = 0;
if(Dfs(1, 1, 1, 0)) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}