시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 30 15 9 60.000%

문제

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

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

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

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 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+XHJcblxyXG48cD5cdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHViZTQ4IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWIzYzRcdWM3YTVcdWM3NDQgXHVkNTZkXHVjMGMxIFx1YjQ1MCBcdWJjODggXHVjYzBkXHViMjk0XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWIzYzRcdWM3YTVcdWM3NDQgXHVjYzBkXHVjNzQwIFx1YjJlNFx1Yzc0YywgXHViM2M0XHVjN2E1XHVjNzQ0IFx1ZDU1YyBcdWJjODggXHViMzU0IFx1Y2MwZFx1YjI5NFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjODg1XHVjNzc0XHViOTdjIFx1YjNjY1x1YjlhY1x1YmE3NCBcdWM1NDhcdWI0MThcdWJhNzAsIFx1YjNjNFx1YzdhNVx1Yzc0NCBcdWNjMGRcdWIyOTQgXHVjNzA0XHVjZTU4XHViMjk0IFx1YjJlNFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YjNjNFx1YzdhNVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjODg1XHVjNzc0XHVjNzU4IFx1YmNjMFx1YWNmYyBcdWQzYzlcdWQ1ODlcdWQ1NThcdWFjOGMgXHVjYzBkXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD4mIzM5OyMmIzM5O1x1YjI5NCBcdWFjODBcdWM4MTVcdWMwYzkgXHVjNzg5XHVkMDZjXHVhYzAwIFx1YmIzYlx1YjI5NCBcdWJkODBcdWJkODRcdWM3NzRcdWFjZTAsICYjMzk7LiYjMzk7XHVjNzQwIFx1YzU0NFx1YmIzNCBcdWI5YzhcdWQwNmNcdWIzYzQgXHVjNWM2XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCAmIzM5OyMmIzM5O1x1Yjg1YyBcdWNjMGRcdWQ3OGMgXHVjODg1XHVjNzc0XHVjNWQwICYjMzk7LiYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWIzYzRcdWM3YTVcdWM3NTggXHVjNzdjXHViZDgwXHVhYzAwIFx1Y2MwZFx1ZDc4Y1x1YjJlNFx1YmE3NCwgXHVhZGY4XHViMzAwXHViODVjICYjMzk7IyYjMzk7XHViOTdjIFx1YzcyMFx1YzljMFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjYxMCwgXHViNDUwIFx1YmM4OCBcdWNjMGRcdWQ3OGMgXHVjZTc4XHVhY2ZjLCBcdWQ1NWMgXHViYzg4IFx1Y2MwZFx1ZDc4YyBcdWNlNzhcdWM3NDAgXHVhZDZjXHViZDg0XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YzdhNVx1Yzc0NCBcdWI0NTAgXHViYzg4IFx1Y2MwZFx1Yzc0MCBcdWM4ODVcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4XHViN2VjXHVkNTVjIFx1Yzg4NVx1Yzc3NCBcdWJhYThcdWM1OTFcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YjNjNFx1YzdhNSBcdWM5MTFcdWM1ZDBcdWMxMWMgJiMzOTsjJiMzOTtcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzcwNFx1Yzc1OCBcdWIzYzRcdWM3YTVcdWM3NDQgXHViNDUwIFx1YmM4OCBcdWNjMGRcdWM3NDAgXHViYWE4XHVjNTkxIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uIy4uIy4uXHJcbi4jIyMjIyMuXHJcbi4jIyMjIyMuXHJcbi4uIy4uIy4uPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoMSAmbGU7IFQgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4ODVcdWM3NzRcdWM3NTggXHVhZTM4XHVjNzc0IExcdWFjZmMgXHViMTA4XHViZTQ0IFcgKDEgJmxlOyBXLCBMICZsZTsgMzAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBMXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgV1x1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgJiMzOTsuJiMzOTtcdWM2NDAgJiMzOTsjJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgJiMzOTsjJiMzOTtcdWIyOTQgXHVhYzgwXHVjODE1IFx1Yzc4OVx1ZDA2Y1x1YWMwMCBcdWJiM2JcdWM3NDAgXHVjZTc4LCAmIzM5Oy4mIzM5O1x1YjI5NCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViM2M0XHVjN2E1XHVjNzU4ICYjMzk7IyYjMzk7IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA1NjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdGFtcCBTdGFtcCIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvc3RhbXAucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM1cHg7IHdpZHRoOjE4OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkJ1cmVhdWNyYXRzIGxvdmUgYnVyZWF1Y3JhY3kuIFRoaXMgYXNzZXJ0aW9uIHNlZW1zIGZhaXJseSBvYnZpb3VzIGJ1dCBhIGxlc3Mgb2J2aW91cyBvYnNlcnZhdGlvbiBpcyB0aGUgYW1vdW50IG9mIHBhcGVyd29yayB0aGlzIG1lYW5zISBXaGVuIHBhcGVyd29yayBpcyBjb21wbGV0ZSwgdGhlIGJ1cmVhdWNyYXQgc3RhbXBzIHRoZSBvZmZpY2lhbCBkb2N1bWVudCB3aXRoIHRoZWlyIG9mZmljaWFsIHN0YW1wIG9mIG9mZmljZS4gU29tZSBidXJlYXVjcmF0cyBhcmUgZXh0cmEgdGhvcm91Z2ggYW5kIHN0YW1wIHRoZSBkb2N1bWVudCBtdWx0aXBsZSB0aW1lcy48XC9wPlxyXG5cclxuPHA+V2UgYXJlIGludGVyZXN0ZWQgcHJpbWFyaWx5IGluIGJ1cmVhdWNyYXRzIHRoYXQgc3RhbXAgdGhlaXIgZG9jdW1lbnRzIHR3aWNlLiBBIGJ1cmVhdWNyYXQgc3RhbXAgdGFrZXMgdXAgc29tZSByZWN0YW5ndWxhciBhcmVhLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgYmVsb3cgaXMgYSBidXJlYXVjcmF0JnJzcXVvO3Mgc3RhbXA6PFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uIy4uIy4uXHJcbi4jIyMjIyMuXHJcbi4uIy4uIy4uPFwvcHJlPlxyXG5cclxuPHA+V2hlbiB0aGUgYnVyZWF1Y3JhdCBzdGFtcHMgdGhlIHBhcGVyIHR3aWNlLCBpdCBpcyBwb3RlbnRpYWxseSBtb3ZlZCB0byBkaWZmZXJlbnQgbG9jYXRpb24gb24gdGhlIHBhcGVyIGJ1dCBub3Qgcm90YXRlZC4gVGhlIHN0YW1wIHdpbGwgYWx3YXlzIGJlIGF4aXMgYWxpZ25lZC48XC9wPlxyXG5cclxuPHA+VGhlICZsc3F1bzsjJnJzcXVvOyBzeW1ib2wgb24gYSBzdGFtcCBjb3ZlcnMgdGhlIHBhcGVyIHdpdGggYmxhY2sgaW5rIGF0IHRoZSBjZWxsIG9uIHRoZSBwYXBlciB0aGF0IGlzIHByZXNzZWQuIEEgJmxzcXVvOy4mcnNxdW87IGRvZXNuJnJzcXVvO3QgbGVhdmUgYW55IG1hcmtzIG9uIHRoZSBwYXBlciBub3IgZG9lcyBpdCByZW1vdmUgYSBtYXJrLiBJZiBhIGNlbGwgb2YgdGhlIHBhcGVyIGlzIG1hcmtlZCB0d2ljZSBpdCBpcyB1bmRpc2Nlcm5hYmxlIGZyb20gYSBjZWxsIHRoYXQgaXMgbWFya2VkIG9uY2UuPFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIGJlIGdpdmVuIGEgcGFwZXIgdGhhdCB3YXMgc3RhbXBlZCB0d2ljZSBieSBhIHN0YW1wLiBZb3VyIHRhc2sgaXMgdG8gZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBudWJzICgjIHN5bWJvbHMpIHRoYXQgY291bGQgaGF2ZSBwb3NzaWJseSBiZWVuIG9uIHRoZSBvcmlnaW5hbCBzdGFtcC4gVGhlIHBhcGVyIGlzIGd1YXJhbnRlZWQgdG8gYmUgc3RhbXBlZCB0d2ljZSBieSB0aGUgZW50aXJlIHN0YW1wLiAoQWxsIG9mIHRoZSBzdGFtcCB3aWxsIGJlIG9uIHRoZSBwYXBlciBpbiBib3RoIHN0YW1waW5ncyk8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUgdGhlIGFib3ZlIHN0YW1wIGNvdWxkIGhhdmUgbWFkZSB0aGUgZm9sbG93aW5nIG1hcmsgb24gcGFwZXI6PFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uIy4uIy4uXHJcbi4jIyMjIyMuXHJcbi4jIyMjIyMuXHJcbi4uIy4uIy4uPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBudW1iZXIgVCByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBwaWVjZXMgb2YgcGFwZXIgdG8gYW5hbHl6ZSwgKDEgJmxlOyBUICZsZTsgMTAwKS4gRm9yIGVhY2ggcGllY2Ugb2YgcGFwZXIsIHRoZXJlIHdpbGwgYmUgdHdvIG51bWJlcnMgTCBhbmQgVyByZXByZXNlbnRpbmcgdGhlIGxlbmd0aCBhbmQgd2lkdGggb2YgdGhlIHBhcGVyLCAoMSAmbHQ7PSBXLCBMICZsdDs9IDMwMCkuIFRoZSBuZXh0IEwgbGluZXMgd2lsbCBlYWNoIGNvbnRhaW4gYSBzdHJpbmcgb2YgbGVuZ3RoIFcuIFRoaXMgc3RyaW5nIHdpbGwgY29uc2lzdCBvZiBvbmx5IHRoZSBjaGFyYWN0ZXJzICZsc3F1bzsuJnJzcXVvOyBhbmQgJmxzcXVvOyMmcnNxdW87LiAmbHNxdW87LiZyc3F1bzsgcmVwcmVzZW50cyBhIHdoaXRlIGNlbGwgb2YgcGFwZXIuICZsc3F1bzsjJnJzcXVvOyByZXByZXNlbnRzIGEgY2VsbCBjb3ZlcmVkIGluIGJsYWNrIGluay48XC9wPlxyXG5cclxuPHA+QXQgbW9zdCAxNSBvZiB0aGUgdGVzdCBjYXNlcyB3aWxsIGhhdmUgYSB3aWR0aCBvciBsZW5ndGggZ3JlYXRlciB0aGFuIDgwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHBpZWNlIG9mIHBhcGVyLCBvdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG51YnMgcG9zc2libGUgb24gdGhlIG9yaWdpbmFsIHN0YW1wLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==