시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 8 4 4 50.000%

문제

Bureaucrats love bureaucracy. This assertion seems fairly obvious but a less obvious observation is the amount of paperwork this means! When paperwork is complete, the bureaucrat stamps the official document with their official stamp of office. Some bureaucrats are extra thorough and stamp the document multiple times.

We are interested primarily in bureaucrats that stamp their documents twice. A bureaucrat stamp takes up some rectangular area.

For example, below is a bureaucrat’s stamp:

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

When the bureaucrat stamps the paper twice, it is potentially moved to different location on the paper but not rotated. The stamp will always be axis aligned.

The ‘#’ symbol on a stamp covers the paper with black ink at the cell on the paper that is pressed. A ‘.’ doesn’t leave any marks on the paper nor does it remove a mark. If a cell of the paper is marked twice it is undiscernable from a cell that is marked once.

You will be given a paper that was stamped twice by a stamp. Your task is to determine the minimum number of nubs (# symbols) that could have possibly been on the original stamp. The paper is guaranteed to be stamped twice by the entire stamp. (All of the stamp will be on the paper in both stampings)

For example the above stamp could have made the following mark on paper:

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

입력

You are given a number T representing the number of pieces of paper to analyze, (1 ≤ T ≤ 100). For each piece of paper, there will be two numbers L and W representing the length and width of the paper, (1 <= W, L <= 300). The next L lines will each contain a string of length W. This string will consist of only the characters ‘.’ and ‘#’. ‘.’ represents a white cell of paper. ‘#’ represents a cell covered in black ink.

At most 15 of the test cases will have a width or length greater than 80.

출력

For each piece of paper, output the minimum number of nubs possible on the original stamp.

예제 입력

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

예제 출력

8
1
5
3
21

힌트