토지 사기극

(...) 예를 들어 이런 이야기를 들은 적이 있습니다. 수도에 사는 어떤 사람이 젬랴노이 발 거리에서 부엌 딸린 방 세 칸짜리 집을 얻었는데, 머리가 어질어질해질 만한 제5차원 같은 것도 전혀 없이 눈 깜짝할 사이에 그것을 부엌 딸린 방 네 칸짜리 집으로 바꿔 놓았습니다. 그저 방 하나를 칸막이로 둘로 나누었을 뿐이지요. 그다음 그는 그 집을 모스크바의 서로 다른 구역에 있는 별개의 두 집, 즉 방 세 칸짜리 하나와 방 두 칸짜리 하나로 바꾸었습니다. 이것만으로도 벌써 방이 다섯 칸이 된다는 것은 당신도 인정하시겠지요. 다시 방 세 칸짜리 집을 부엌 딸린 방 두 칸짜리 별개의 집 둘로 바꾸어, 보시다시피 방 여섯 칸의 주인이 되었습니다. 물론 모스크바 곳곳에 어수선하게 흩어져 있기는 했지만요. 그가 막 마지막이자 가장 화려한 묘기를 부리려던 참이었습니다. 모스크바 여기저기의 방 여섯 칸을 젬랴노이 발 거리의 방 다섯 칸짜리 집 하나와 바꾸고 싶다는 광고를 신문에 냈지요. 그런데 그의 활동은 전적으로 그와는 무관한 이유로 멈추고 말았습니다. 아마 지금도 어딘가에서 방 한 칸쯤은 차지하고 있겠지만, 그곳이 모스크바가 아니라는 것만은 장담할 수 있습니다. 자, 이런 사람을 두고 머리가 잘 돌아가는 사람이라 하는 겁니다. 그런데 당신은 여기서 제5차원 이야기나 하고 있군요!

미하일 불가코프, 「거장과 마르가리타」

바이타자르는 직사각형 토지를 가진 행복한 지주로, 측량을 위해 그 땅을 $m \times n$개의 단위 정사각형으로 나누어 두었다. 그런데 각 정사각형은 초원이거나 늪이다. 바이타자르는 이 땅을 팔고 카리브해로 떠나고 싶어 한다. 당분간 바이토시아로 돌아올 생각이 없으므로, 같은 땅을 여러 사람에게 동시에 파는 데에도 아무런 거리낌이 없다.

각 매수인은 변이 단위 정사각형의 변과 일치하는 직사각형 조각 하나를 살 수 있다. 다만 아무도 자기 조각 안에 늪이 있는 것은 용납하지 않으므로, 모든 조각은 초원 칸으로만 이루어져야 한다. 서로 다른 사람에게 판 조각끼리는 겹쳐도 되지만, 어떤 두 조각도 오른쪽 아래 모서리가 같아서는 안 된다(바이토시아의 관리들은 영민하기로 소문나지는 않았어도 그것만큼은 틀림없이 알아챌 것이다). 조각의 값은 바이토시아 법에 따라 그 둘레에 비례한다. 그렇다면 바이타자르가 벌 수 있는 최대 금액은 얼마인가? (조각의 오른쪽 아래 모서리란 그 조각에서 행 번호와 열 번호가 모두 가장 큰 초원 칸을 말한다.)

표준 입력의 첫 줄에는 테스트의 개수 $T$가 주어진다. 이어서 $T$개의 테스트가 다음 형식으로 주어진다. 각 테스트의 첫 줄에는 토지의 세로 길이와 가로 길이를 나타내는 두 정수 $n$과 $m$ ($1 \le n, m \le 2000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 $m$개의 문자가 있으며, $i$번째 줄의 $j$번째 문자는 좌표 $(i, j)$의 칸이 초원이면 ., 늪이면 #이다.

각 테스트마다 바이타자르가 팔 수 있는 조각들의 둘레의 최대 합을 한 정수로 한 줄에 출력한다.