도장 도장

시간 제한10초메모리 제한256 MB

요약

두 번의 평행 찍기로 주어진 종이를 만들 수 있는 스탬프 중 잉크 칸이 가장 적은 경우를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그래프, 완전 탐색, 행렬
정답자: 아직 제출이 없습니다

문제

직사각형 모양의 도장이 있다. 도장에서 잉크가 묻는 칸은 '#', 묻지 않는 칸은 '.'로 나타낸다. 아래는 도장의 예시다.

..#..#..
.######.
..#..#..

빈 종이에 이 도장을 정확히 두 번 찍는다. 종이도 도장도 돌리지 않으며, 도장은 항상 종이의 변과 평행하게, 종이 밖으로 벗어나지 않게 찍는다. 두 번 찍는 위치는 같아도 되고 달라도 된다.

도장의 '#' 칸이 닿은 종이 칸에는 잉크가 묻어 '#'가 된다. '.' 칸이 닿은 칸은 그대로 남으므로, 이미 잉크가 묻은 칸은 '#'를 유지한다. 잉크가 두 번 묻은 칸과 한 번 묻은 칸은 구분할 수 없다.

도장을 두 번 찍은 결과인 종이가 주어진다. 이 종이를 만들 수 있는 도장 중에서 '#'의 개수가 가장 적은 것을 찾아 그 개수를 구한다.

아래는 위 도장으로 만들 수 있는 종이 하나다.

..#..#..
.######.
.######.
..#..#..

입력

첫째 줄에 테스트 케이스의 개수 $T$ ( $1 \le T \le 100$ )가 주어진다. 각 테스트 케이스의 첫째 줄에는 종이의 세로 길이 $L$ 과 가로 길이 $W$ ( $1 \le L, W \le 300$ )가 주어진다. 이어지는 $L$ 개의 줄에는 길이가 $W$ 인 문자열이 주어진다. 문자열은 '.'와 '#'로만 이루어지며, '#'는 잉크가 묻은 칸, '.'는 빈 칸이다.

출력

각 테스트 케이스마다 종이를 만들 수 있는 도장의 '#' 개수 중 가장 작은 값을 한 줄에 출력한다. 잉크가 묻은 칸이 하나도 없는 종이라면 0을 출력한다.

예제2

예제 1

입력

5
4 8
..#..#..
.######.
.######.
..#..#..
3 3
...
.#.
...
2 6
.#####
#####.
2 5
.#.#.
#.#.#
6 6
###.##
#.####
######
######
#.####
######

예상 출력

예제 2

입력

3
3 5
#.#.#
.....
#.#.#
5 5
#...#
.....
..#..
.....
#...#
4 4
....
....
....
....

예상 출력

3
5
0