시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 18 7 7 53.846%

문제

백준이는 도장을 좋아한다. 백준이가 사용하는 도장은 직사각형 모양이며, 찍히는 부분은 '#' 기호를 사용한다. 예를 들어, 아래 그림은 백준이의 도장의 예시이다.

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

백준이는 빈 종이에 도장을 항상 두 번 찍는다. 먼저, 종이에 도장을 찍은 다음, 도장을 한 번 더 찍는다. 이 때, 종이를 돌리면 안되며, 도장을 찍는 위치는 다를 수도 있다. 또, 도장은 항상 종이의 변과 평행하게 찍는다.

'#'는 검정색 잉크가 묻는 부분이고, '.'은 아무 마크도 없는 부분이다. 만약, '#'로 찍힌 종이에 '.'로 표시된 도장의 일부가 찍힌다면, 그대로 '#'를 유지하게 된다. 또, 두 번 찍힌 칸과, 한 번 찍힌 칸은 구분할 수 없다.

도장을 두 번 찍은 종이가 주어졌을 때, 그러한 종이 모양을 만드는 도장 중에서 '#'의 개수가 가장 작은 것을 구하는 프로그램을 작성하시오.

예를 들어, 아래 그림은 위의 도장을 두 번 찍은 모양 중 하나이다.

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

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 종이의 길이 L과 너비 W (1 ≤ W, L ≤ 300)가 주어진다. 다음 L개의 줄에는 길이가 W인 문자열이 주어진다. 문자열은 '.'와 '#'로 이루어져 있으며, '#'는 검정 잉크가 묻은 칸, '.'는 빈 칸을 나타낸다.

출력

각각의 테스트 케이스마다 가능한 도장의 '#' 개수가 가장 작은 것을 출력한다. 

예제 입력

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

예제 출력

8
1
5
3
21

힌트