분리된 기계

Bytegate 기계는 Bajtazar가 만든 최신 발명품이다. 기계는 두 부분으로 이루어져 있고, Bajtazar는 이 둘을 절대 떼어 놓을 수 없다고 자랑했다. 두 살배기 아들 Bajtu\u015b가 그 말이 틀렸다는 것을 곧 증명하려 한다.

기계의 초기 상태는 A, B, .으로 채워진 $n \times m$ 배열이다. A는 첫 번째 부분, B는 두 번째 부분, .은 빈 칸을 뜻한다.

+-+-+-+-+-+
|B|B|A|A|.|
+-+-+-+-+-+
|.|B|B|A|A|
+-+-+-+-+-+
|A|.|B|B|A|
+-+-+-+-+-+
|A|.|.|B|A|
+-+-+-+-+-+
|A|A|A|A|A|
+-+-+-+-+-+

배열에는 A가 하나 이상, B가 하나 이상 있다. 두 부분은 모두 연결되어 있다. 임의의 두 A 칸은 A 칸만 지나는 경로로 이어지며, 연속한 두 칸은 변을 공유한다. B도 같은 방식으로 연결되어 있다.

Baj\u0074u\u015b는 B 부분을 정한 방향으로 당긴다. 이동은 길이 $q$의 문자열로 주어지며, 각 문자는 북쪽 N, 남쪽 S, 동쪽 E, 서쪽 W 중 하나이다. 매번 B를 당기다가 한 칸 더 가면 두 부분이 겹치게 될 때까지 움직인다. 그 방향으로 끝없이 움직일 수 있다면 두 부분이 분리된 것이다. 한 번 분리된 기계는 계속 분리된 상태로 남는다. Bajtu\u015b가 이동 중 어느 시점에든 기계를 분리하는지 판단하라.

첫 줄에 테스트 케이스 수 $z$ ($1 \le z \le 1000$)가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $n, m, q$ ($1 \le n, m \le 10$, $1 \le q \le 100$)가 주어진다. 이어서 $n$줄에 걸쳐 길이 $m$의 문자열이 주어지며, 문자는 A, B, .만 쓴다. 두 부분은 모두 비어 있지 않고 연결되어 있다. 마지막 줄에는 N, S, E, W로 이루어진 $q$개의 문자가 주어진다.

각 테스트 케이스마다 Bajtu\u015b가 기계를 분리하면 TAK, 그렇지 않으면 NIE를 출력한다.

두 번째 테스트 케이스에서는 네 번째 이동에서 기계가 분리된다.