옷장 방 (라지)

의류 회사의 파스칼 사장은 재고 옷을 보관하려고 가로 $W$, 세로 $H$인 창고를 빌렸고, 그 창고에 옷장을 최대한 많이 설치하기로 했다. 창고 바닥은 $1 \times 1$ 타일 $W \times H$장으로 덮여 있고, 창고 출입문은 바깥 둘레의 타일 하나에 딱 붙어 있다. 창고 안에는 기둥이 몇 개 서 있다(한 개도 없을 수 있다).

옷장은 직육면체이고 가로가 2, 세로가 1이라서 타일 두 장을 정확히 덮는다. 가로가 2인 두 면 중 한쪽에 문이 달려 있고, 그 면을 정면에서 보면 문은 왼쪽 절반을 차지한다.

옷을 꺼내는 일은 로봇이 한다. 그래서 창고 출입문에서 각 옷장의 문 바로 앞 타일까지 로봇이 지나갈 수 있는 경로가 있어야 한다. 로봇은 크기가 $1 \times 1$이고 타일에서 상하좌우로 인접한 타일로 움직인다. 옷장이나 기둥이 놓인 타일에는 올라갈 수 없다.

사장은 꼼꼼한 성격이라 옷장을 반드시 타일 두 장 위에 딱 맞게 놓으라고 지시했다. 그래서 옷장 하나를 놓는 방법은 다음 네 가지로 정해진다. C는 옷장 본체이고, X는 옷장 문을 열 수 있도록 아무것도 놓여서는 안 되는 자리다. .은 나머지 타일이다.

....
.CC.
.X..
....

....
..X.
.CC.
....

....
.XC.
..C.
....

....
.C..
.CX.
....

X 자리는 창고 안에 있어야 하고, 기둥이 없어야 하며, 어떤 옷장도 그 자리를 덮어서는 안 된다. 로봇은 창고 출입문에 붙은 타일에서 출발해 모든 옷장의 X 자리까지 갈 수 있어야 한다. 옷장 두 개가 같은 X 자리를 함께 써도 된다.

이때 사장이 창고에 설치할 수 있는 옷장 개수의 최댓값을 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다.

각 테스트 케이스의 첫째 줄에는 창고의 세로 $H$와 가로 $W$가 공백으로 구분되어 주어진다. 이어서 길이가 $W$인 문자열이 $H$줄 주어진다.

$i$번째 줄의 $j$번째 문자 $c_{i,j}$는 타일 $(i, j)$의 상태를 나타낸다. 그 타일이 창고 출입문에 붙어 있으면 D, 기둥이 있으면 X, 둘 다 아니면 .이다. D는 테스트 케이스마다 정확히 한 번 나온다.

제한

• $1 \le T \le 100$
• $1 \le H \le 30$
• $1 \le W \le 5$

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 조건에 맞게 설치할 수 있는 옷장 개수의 최댓값이다.