기름 수거

한 기업이 수익성 높은 해상 기름 수거 사업을 운영한다. 바다 위에는 커다란 원유 띠가 떠 있어 걷어내기를 기다리고 있다. 특수 비행기가 수면을 훑으며 기름을 걷어내는데, 한 번의 수거는 가로 또는 세로로 놓인 10 m × 20 m 직사각형 영역을 덮는다. 각 칸은 한 변이 10 m인 정사각형이므로, 한 번의 수거는 격자에서 상하 또는 좌우로 인접한 두 칸을 덮는 것과 같다. 이 두 칸은 모두 기름이어야 하며, 하나라도 순수한 바닷물이면 걷어낸 기름이 오염되어 상품 가치가 없어진다.

기름 띠의 지도가 주어질 때, 최대 몇 번의 수거를 할 수 있는지 구하여라. 지도는 $N \times N$ 격자이며, 각 칸은 10 m 크기의 정사각형 수면으로, 기름 칸 또는 순수한 물 칸으로 표시된다. 수거한 직사각형들은 서로 겹칠 수 없다.

첫째 줄에 테스트 케이스의 수 $K$ ($1 \le K \le 100$)가 주어진다. 각 테스트 케이스의 첫째 줄에는 정사각 격자의 크기 $N$ ($1 \le N \le 600$)이 주어진다. 이어지는 $N$개의 줄에는 각각 격자의 한 행을 나타내는 $N$개의 문자가 주어진다. 문자 #는 기름 칸을, .는 순수한 물 칸을 의미한다.

각 테스트 케이스마다 한 줄씩, 정확히 Case X: M 형식으로 출력한다. 여기서 $X$는 (1부터 시작하는) 테스트 케이스 번호이고, $M$은 걷어낼 수 있는 기름 수거의 최대 횟수이다.