Time Limit: 1000 MS Memory Limit: 32726 K


Description

在一个古老的迷宫中,小明找到了一把可以离开迷宫的钥匙。但是此时迷宫开始坍塌,因此小明需要尽快这个迷宫。
迷宫为一个长方形,其大小为Nxm。迷宫中有一扇门,但是这扇门是关着的,只有在第t秒才会打开一小段时间(小于1秒)。因此小明需要刚好t秒的时候到达门口。每秒小明都可以移动到相邻的上、下、左、右方块中的一个位置。一旦他走到下一个位置,上一个位置的地面便开始塌陷(因此他无法在相同位置停留超过1秒,也不能回到走过的位置)。小明可以安全的离开这个迷宫吗?请帮他算一算。

Input

输入包含多个测试样例,输入的第一行为测试样例的数量,从第二行开始,每个测试样例的第一行有三个整数n,m,t(1 < n, m < 7; 0 < t < 50),分别代表迷宫的大小和门开启的时间。 接下来的n行定义了迷宫的布局,每行有m个字符。每个字符的含义如下:

'X': 一块墙,无法通过;
'S': 小明的起始地点;
'D': 门的位置;
'.': 可以通过的块。

Output

每组样例输出一行,如果小明可以走出迷宫则输出"YES",否则输出"NO"。

Sample Input

2
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D

Sample Output

NO
YES