좀비 폭파!

살려주세요!!! 좀비들이 몰려오고 있습니다! 좀비 침공이 시작되었고, 그들의 군단이 우리의 마지막 방어선을 향해 진격하고 있습니다.

하지만 아직 희망은 있습니다. 다가올 재앙에 대비해, 여러분은 전장에 다수의 가변 폭발 지뢰(ACM)를 설치해 두었습니다. 이 지뢰들은 모두 동시에 터뜨릴 수 있으며, 폭발 반경은 여러분이 하나의 값으로 지정합니다. 각 지뢰는 자신의 폭발 반경 안에 있는 모든 좀비를 즉시 태워 없앱니다.

위성 사진으로 현재 상황을 담은 지도를 얻었습니다. 지도는 한 변의 길이가 1인 정사각형 칸들로 나뉜 직사각형 영역입니다. 각 칸은 비어 있거나(.), 좀비(Z)가 있거나, 지뢰(M)가 있습니다.

어떤 좀비가 있는 칸의 중심과 어떤 지뢰가 있는 칸의 중심 사이의 유클리드 거리가 폭발 반경 이하이면, 그 좀비는 그 지뢰에 의해 소각됩니다. 다시 말해, 각 좀비는 폭발 반경이 자신과 가장 가까운 지뢰까지의 거리 이상일 때에만 제거됩니다. 부수적 피해를 최소화하기 위해, 모든 좀비를 소각할 수 있는 가장 작은 폭발 반경으로 지뢰를 터뜨려야 합니다. 주어진 침공 상황에서 그 최소 폭발 반경은 얼마입니까?

첫째 줄에 침공 시나리오(지도)의 개수 $N$이 주어집니다.

각 시나리오는 지도의 너비와 높이를 나타내는 두 정수 $w$와 $h$ ($1 \le w, h \le 2000$)가 공백으로 구분되어 한 줄에 주어지는 것으로 시작합니다. 이어서 $h$개의 줄에 각각 $w$개의 문자가 주어져 지도를 나타냅니다.

• Z는 좀비를 나타냅니다.
• M은 지뢰를 나타냅니다.
• .은 빈 칸을 나타냅니다.

모든 지도에는 적어도 하나의 좀비(Z)와 하나의 지뢰(M)가 존재합니다.

각 시나리오마다, 모든 좀비를 소각하기 위해 필요한 가장 작은 폭발 반경의 제곱 값을 한 줄에 하나의 정수로 출력합니다.

즉, 각 좀비에 대해 그 좀비와 가장 가까운 지뢰까지의 유클리드 거리의 제곱을 구한 뒤(칸 좌표의 차이를 $\Delta x$, $\Delta y$라 하면 그 값은 $\Delta x^2 + \Delta y^2$입니다), 모든 좀비에 대한 이 값들의 최댓값을 출력합니다. 실제 최소 폭발 반경은 이 값의 제곱근입니다.

(칸 좌표의 차이는 항상 정수이므로 이 제곱 값도 항상 정수입니다. 부동소수점 오차를 피하기 위해, 반경 자체가 아니라 그 제곱을 정수로 출력합니다.)