관광객

게으른 관광객이 도시에서 필요 이상으로 걷지 않으면서 가능한 한 많은 흥미로운 장소를 방문하려고 합니다. 그는 도시의 북서쪽(왼쪽 위) 모서리에 있는 호텔에서 출발하여 남동쪽(오른쪽 아래) 모서리까지 걸어간 뒤 다시 호텔로 돌아옵니다. 남동쪽 모서리로 갈 때는 동쪽 또는 남쪽으로만 이동하고, 북서쪽 모서리로 돌아올 때는 북쪽 또는 서쪽으로만 이동합니다. 도시의 일부 구역은 막혀 있어 이동이 자유롭지 않습니다.

흥미로운 장소와 막힌 구역이 표시된 2차원 격자 형태의 도시 지도가 주어질 때, 그가 방문할 수 있는 흥미로운 장소의 최대 개수를 구하세요. 두 번 이상 방문한 장소는 한 번만 셉니다.

첫째 줄에 테스트 케이스의 수(최대 $20$)가 주어집니다. 각 테스트 케이스의 첫째 줄에는 도시 지도의 너비와 높이를 나타내는 두 정수 $W$와 $H$ ($2 \le W, H \le 100$)가 주어집니다. 이어서 $H$개의 줄에 각각 $W$개의 문자로 이루어진 문자열이 주어지며, 각 문자의 의미는 다음과 같습니다.

• . 걸을 수 있는 구역
• * 흥미로운 장소(걸을 수도 있음)
• # 막힌 구역

왼쪽 위 모서리(출발점이자 도착점)와 오른쪽 아래 모서리(반환점)는 걸을 수 있으며, 두 지점 사이에는 길이가 $H + W - 2$인 이동 가능한 경로가 존재한다고 가정해도 됩니다.

각 테스트 케이스마다 관광객이 방문할 수 있는 흥미로운 장소의 최대 개수를 정수 하나로 한 줄에 출력하세요.