시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 256 MB135473532.710%

문제

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

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

8
1
5
3
21
W3sicHJvYmxlbV9pZCI6IjEwNTY2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2M0XHVjN2E1IFx1YjNjNFx1YzdhNSIsImRlc2NyaXB0aW9uIjoiPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1YjNjNFx1YzdhNVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YWMwMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViM2M0XHVjN2E1XHVjNzQwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NzRcdWJhNzAsIFx1Y2MwZFx1ZDc4OFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NDAgJiMzOTsjJiMzOTsgXHVhZTMwXHVkNjM4XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWJjMzFcdWM5MDBcdWM3NzRcdWM3NTggXHViM2M0XHVjN2E1XHVjNzU4IFx1YzYwOFx1YzJkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuLi4jLi4jLi5cclxuLiMjIyMjIy5cclxuLi4jLi4jLi48XC9wcmU+XHJcblxyXG48cD5cdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHViZTQ4IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWIzYzRcdWM3YTVcdWM3NDQgXHVkNTZkXHVjMGMxIFx1YjQ1MCBcdWJjODggXHVjYzBkXHViMjk0XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWIzYzRcdWM3YTVcdWM3NDQgXHVjYzBkXHVjNzQwIFx1YjJlNFx1Yzc0YywgXHViM2M0XHVjN2E1XHVjNzQ0IFx1ZDU1YyBcdWJjODggXHViMzU0IFx1Y2MwZFx1YjI5NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM4ODVcdWM3NzRcdWI5N2MgXHViM2NjXHViOWFjXHViYTc0IFx1YzU0OFx1YjQxOFx1YmE3MCwgXHViM2M0XHVjN2E1XHVjNzQ0IFx1Y2MwZFx1YjI5NCBcdWM3MDRcdWNlNThcdWIyOTQgXHViMmU0XHViOTdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHViM2M0XHVjN2E1XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM4ODVcdWM3NzRcdWM3NTggXHViY2MwXHVhY2ZjIFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YWM4YyBcdWNjMGRcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiYjMzk7IyYjMzk7XHViMjk0IFx1YWM4MFx1YzgxNVx1YzBjOSBcdWM3ODlcdWQwNmNcdWFjMDAgXHViYjNiXHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NFx1YWNlMCwgJiMzOTsuJiMzOTtcdWM3NDAgXHVjNTQ0XHViYjM0IFx1YjljOFx1ZDA2Y1x1YjNjNCBcdWM1YzZcdWIyOTQgXHViZDgwXHViZDg0XHVjNzc0XHViMmU0LiBcdWI5Y2NcdWM1N2QsICYjMzk7IyYjMzk7XHViODVjIFx1Y2MwZFx1ZDc4YyBcdWM4ODVcdWM3NzRcdWM1ZDAgJiMzOTsuJiMzOTtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDFjIFx1YjNjNFx1YzdhNVx1Yzc1OCBcdWM3N2NcdWJkODBcdWFjMDAgXHVjYzBkXHVkNzhjXHViMmU0XHViYTc0LCBcdWFkZjhcdWIzMDBcdWI4NWMgJiMzOTsjJiMzOTtcdWI5N2MgXHVjNzIwXHVjOWMwXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHViYzg4IFx1Y2MwZFx1ZDc4YyBcdWNlNzhcdWFjZmMsIFx1ZDU1YyBcdWJjODggXHVjYzBkXHVkNzhjIFx1Y2U3OFx1Yzc0MCBcdWFkNmNcdWJkODRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjN2E1XHVjNzQ0IFx1YjQ1MCBcdWJjODggXHVjYzBkXHVjNzQwIFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjODg1XHVjNzc0IFx1YmFhOFx1YzU5MVx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViM2M0XHVjN2E1IFx1YzkxMVx1YzVkMFx1YzExYyAmIzM5OyMmIzM5O1x1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNzA0XHVjNzU4IFx1YjNjNFx1YzdhNVx1Yzc0NCBcdWI0NTAgXHViYzg4IFx1Y2MwZFx1Yzc0MCBcdWJhYThcdWM1OTEgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuLi4jLi4jLi5cclxuLiMjIyMjIy5cclxuLiMjIyMjIy5cclxuLi4jLi4jLi48XC9wcmU+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgxICZsZTsgVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWFlMzhcdWM3NzQgTFx1YWNmYyBcdWIxMDhcdWJlNDQgVyAoMSAmbGU7IFcsIEwgJmxlOyAzMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIExcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBXXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAmIzM5Oy4mIzM5O1x1YzY0MCAmIzM5OyMmIzM5O1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCAmIzM5OyMmIzM5O1x1YjI5NCBcdWFjODBcdWM4MTUgXHVjNzg5XHVkMDZjXHVhYzAwIFx1YmIzYlx1Yzc0MCBcdWNlNzgsICYjMzk7LiYjMzk7XHViMjk0IFx1YmU0OCBcdWNlNzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIzYzRcdWM3YTVcdWM3NTggJiMzOTsjJiMzOTsgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDU2NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0YW1wIFN0YW1wIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zdGFtcC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzVweDsgd2lkdGg6MTg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QnVyZWF1Y3JhdHMgbG92ZSBidXJlYXVjcmFjeS4gVGhpcyBhc3NlcnRpb24gc2VlbXMgZmFpcmx5IG9idmlvdXMgYnV0IGEgbGVzcyBvYnZpb3VzIG9ic2VydmF0aW9uIGlzIHRoZSBhbW91bnQgb2YgcGFwZXJ3b3JrIHRoaXMgbWVhbnMhIFdoZW4gcGFwZXJ3b3JrIGlzIGNvbXBsZXRlLCB0aGUgYnVyZWF1Y3JhdCBzdGFtcHMgdGhlIG9mZmljaWFsIGRvY3VtZW50IHdpdGggdGhlaXIgb2ZmaWNpYWwgc3RhbXAgb2Ygb2ZmaWNlLiBTb21lIGJ1cmVhdWNyYXRzIGFyZSBleHRyYSB0aG9yb3VnaCBhbmQgc3RhbXAgdGhlIGRvY3VtZW50IG11bHRpcGxlIHRpbWVzLjxcL3A+XHJcblxyXG48cD5XZSBhcmUgaW50ZXJlc3RlZCBwcmltYXJpbHkgaW4gYnVyZWF1Y3JhdHMgdGhhdCBzdGFtcCB0aGVpciBkb2N1bWVudHMgdHdpY2UuIEEgYnVyZWF1Y3JhdCBzdGFtcCB0YWtlcyB1cCBzb21lIHJlY3Rhbmd1bGFyIGFyZWEuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBiZWxvdyBpcyBhIGJ1cmVhdWNyYXQmcnNxdW87cyBzdGFtcDo8XC9wPlxyXG5cclxuPHByZT5cclxuLi4jLi4jLi5cclxuLiMjIyMjIy5cclxuLi4jLi4jLi48XC9wcmU+XHJcblxyXG48cD5XaGVuIHRoZSBidXJlYXVjcmF0IHN0YW1wcyB0aGUgcGFwZXIgdHdpY2UsIGl0IGlzIHBvdGVudGlhbGx5IG1vdmVkIHRvIGRpZmZlcmVudCBsb2NhdGlvbiBvbiB0aGUgcGFwZXIgYnV0IG5vdCByb3RhdGVkLiBUaGUgc3RhbXAgd2lsbCBhbHdheXMgYmUgYXhpcyBhbGlnbmVkLjxcL3A+XHJcblxyXG48cD5UaGUgJmxzcXVvOyMmcnNxdW87IHN5bWJvbCBvbiBhIHN0YW1wIGNvdmVycyB0aGUgcGFwZXIgd2l0aCBibGFjayBpbmsgYXQgdGhlIGNlbGwgb24gdGhlIHBhcGVyIHRoYXQgaXMgcHJlc3NlZC4gQSAmbHNxdW87LiZyc3F1bzsgZG9lc24mcnNxdW87dCBsZWF2ZSBhbnkgbWFya3Mgb24gdGhlIHBhcGVyIG5vciBkb2VzIGl0IHJlbW92ZSBhIG1hcmsuIElmIGEgY2VsbCBvZiB0aGUgcGFwZXIgaXMgbWFya2VkIHR3aWNlIGl0IGlzIHVuZGlzY2VybmFibGUgZnJvbSBhIGNlbGwgdGhhdCBpcyBtYXJrZWQgb25jZS48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgYmUgZ2l2ZW4gYSBwYXBlciB0aGF0IHdhcyBzdGFtcGVkIHR3aWNlIGJ5IGEgc3RhbXAuIFlvdXIgdGFzayBpcyB0byBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG51YnMgKCMgc3ltYm9scykgdGhhdCBjb3VsZCBoYXZlIHBvc3NpYmx5IGJlZW4gb24gdGhlIG9yaWdpbmFsIHN0YW1wLiBUaGUgcGFwZXIgaXMgZ3VhcmFudGVlZCB0byBiZSBzdGFtcGVkIHR3aWNlIGJ5IHRoZSBlbnRpcmUgc3RhbXAuIChBbGwgb2YgdGhlIHN0YW1wIHdpbGwgYmUgb24gdGhlIHBhcGVyIGluIGJvdGggc3RhbXBpbmdzKTxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSB0aGUgYWJvdmUgc3RhbXAgY291bGQgaGF2ZSBtYWRlIHRoZSBmb2xsb3dpbmcgbWFyayBvbiBwYXBlcjo8XC9wPlxyXG5cclxuPHByZT5cclxuLi4jLi4jLi5cclxuLiMjIyMjIy5cclxuLiMjIyMjIy5cclxuLi4jLi4jLi48XC9wcmU+XHJcbiIsImlucHV0IjoiPHA+WW91IGFyZSBnaXZlbiBhIG51bWJlciBUIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHBpZWNlcyBvZiBwYXBlciB0byBhbmFseXplLCAoMSAmbGU7IFQgJmxlOyAxMDApLiBGb3IgZWFjaCBwaWVjZSBvZiBwYXBlciwgdGhlcmUgd2lsbCBiZSB0d28gbnVtYmVycyBMIGFuZCBXIHJlcHJlc2VudGluZyB0aGUgbGVuZ3RoIGFuZCB3aWR0aCBvZiB0aGUgcGFwZXIsICgxICZsdDs9IFcsIEwgJmx0Oz0gMzAwKS4gVGhlIG5leHQgTCBsaW5lcyB3aWxsIGVhY2ggY29udGFpbiBhIHN0cmluZyBvZiBsZW5ndGggVy4gVGhpcyBzdHJpbmcgd2lsbCBjb25zaXN0IG9mIG9ubHkgdGhlIGNoYXJhY3RlcnMgJmxzcXVvOy4mcnNxdW87IGFuZCAmbHNxdW87IyZyc3F1bzsuICZsc3F1bzsuJnJzcXVvOyByZXByZXNlbnRzIGEgd2hpdGUgY2VsbCBvZiBwYXBlci4gJmxzcXVvOyMmcnNxdW87IHJlcHJlc2VudHMgYSBjZWxsIGNvdmVyZWQgaW4gYmxhY2sgaW5rLjxcL3A+XHJcblxyXG48cD5BdCBtb3N0IDE1IG9mIHRoZSB0ZXN0IGNhc2VzIHdpbGwgaGF2ZSBhIHdpZHRoIG9yIGxlbmd0aCBncmVhdGVyIHRoYW4gODAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcGllY2Ugb2YgcGFwZXIsIG91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2YgbnVicyBwb3NzaWJsZSBvbiB0aGUgb3JpZ2luYWwgc3RhbXAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==