트로이 목마

트로이와 아테네 사이의 전쟁이 끝난 뒤, 그리스군은 거대한 나무 말을 남기고 철수한 척했습니다. 트로이인들은 말 안에 숨은 병사를 확인하지 않고 성 안으로 끌어들였고, 결국 함락당했습니다.

이 문제에서는 트로이인들이 했어야 할 일을 합니다. 말 내부를 순찰한 경로를 바탕으로, 아직 방문하지 않은 공간 가운데 그리스 병사 한 명(크기 s칸)을 숨길 수 있는 연결 영역이 몇 개인지 세면 됩니다.

말은 h행 w열 직사각형 격자로 표현합니다. 각 트로이 병사는 왼쪽 아래 칸에서 출발해 l, r, u, d 문자로 이동하며 지나간 모든 칸을 순찰합니다. 순찰하지 않은 칸들 가운데 상하좌우로 연결된 덩어리를 cavity라고 부릅니다. 병사는 몸을 구부릴 수 있으므로, cavity의 칸 수가 s 이상이면 그 안에 한 명을 숨길 수 있다고 봅니다.

첫 줄에 테스트 데이터 개수 K가 주어집니다.

각 데이터셋은 다음 형식입니다.

첫 줄에 네 정수 h, w, s, n이 공백으로 구분되어 주어집니다. h와 w는 격자의 높이와 너비(1 ≤ h, w ≤ 30)이고, s는 그리스 병사가 차지하는 칸 수(1 ≤ s ≤ hw), n은 순찰 병사 수(1 ≤ n ≤ 100)입니다.

이어서 n줄에 각 병사의 이동 경로가 주어집니다. 경로는 최대 100글자이며, 각 글자는 l, r, u, d 중 하나로 왼쪽, 오른쪽, 위, 아래 이동을 뜻합니다. 모든 병사는 왼쪽 아래 칸에서 출발하며, 경로 도중 격자 밖으로 나가지 않습니다.

각 데이터셋마다 Data Set x:를 한 줄에 출력하고(x는 1부터 시작), 다음 줄에 크기 s 이상인 cavity의 개수를 출력합니다. 각 데이터셋 출력 뒤에는 빈 줄을 한 줄 넣습니다.