동굴 탐험

한 탐험가가 어느 동굴의 모든 복도를 지나갔다고 주장한다. 각 복도는 곧은 수평 또는 수직 선분이다. 탐험가가 어떤 복도의 점 중 최소한 하나에 (지나가면서라도) 머문 적이 있으면 그 복도는 방문한 것으로 센다. 탐험가의 이동 경로를 시뮬레이션하여, 한 번도 방문하지 않은 복도가 몇 개인지 세어 그의 주장을 확인하여라.

탐험가는 주어진 입구 지점에서 주어진 방향을 향한 채 출발하며, 경로의 방향이 바뀔 수 있는 모든 지점에서 항상 같은 규칙을 적용한다: 왼쪽으로 돌 수 있으면 왼쪽으로 돌고, 그럴 수 없으면 직진하고, 그럴 수도 없으면 오른쪽으로 돌고, 그것도 안 되면 뒤로 돈다. 어떤 방향으로 갈 수 있다는 것은 현재 지점에서 그 방향으로 복도가 이어져 있다는 뜻이다. 왼쪽과 오른쪽은 현재 진행 방향을 기준으로 하며, 왼쪽으로 도는 것은 반시계 방향으로 $90^\circ$ 회전하는 것이다(동쪽을 향할 때 왼쪽은 북쪽, 북쪽을 향할 때 왼쪽은 서쪽, 서쪽을 향할 때 왼쪽은 남쪽, 남쪽을 향할 때 왼쪽은 동쪽). 탐험은 그가 입구 지점에 두 번째로 도달하는 순간 끝난다(출발할 때 그곳에 있던 것을 첫 번째로 센다).

서로 다른 두 수직 복도는 공통점을 갖지 않고, 서로 다른 두 수평 복도도 공통점을 갖지 않는다. 다만 수평 복도와 수직 복도는 교차하거나 맞닿을 수 있다. 입구 지점은 결코 두 복도의 교차점에 놓이지 않으며, 탐험가는 항상 주어진 시작 방향으로 나아갈 수 있다.

첫 줄에 지도의 개수를 나타내는 정수 $T$ ($T \le 20$)가 주어진다. 각 지도는 다음과 같이 주어진다.

• 첫 줄에 복도의 개수를 나타내는 정수 $N$ ($N \le 1000$)이 주어진다. 수직 복도는 최대 $500$개, 수평 복도는 최대 $500$개이다.
• 다음 $N$개의 줄에 각각 복도 하나가 주어진다. 수평 복도는 H 뒤에 하나의 $y$좌표와 두 개의 $x$좌표로 주어진다. 수직 복도는 V 뒤에 하나의 $x$좌표와 두 개의 $y$좌표로 주어진다.
• 지도의 마지막 줄에는 입구 지점의 $x$좌표와 $y$좌표, 그리고 시작 방향이 주어진다. 방향은 W(서쪽, $-x$), E(동쪽, $+x$), N(북쪽, $+y$), S(남쪽, $-y$) 중 하나이다.

모든 좌표는 절댓값이 $32767$을 넘지 않는 정수이다.

각 지도마다, 탐험가가 한 번도 방문하지 않은 복도의 개수를 한 줄에 하나씩 출력한다.

이 그림은 첫 번째 예제의 첫 지도에 나온 동굴을 나타낸 것이다.