산불

극심한 가뭄은 산불 위험을 크게 높인다. 덥고 건조한 여름이 지나면 숲은 불쏘시개처럼 변해 쉽게 불이 붙고 빠르게 탄다. 이 문제에서는 불이 지형을 따라 번지는 과정을 시뮬레이션하여, 초목이 있는 전체 영역이 모두 불타기까지 걸리는 시간을 구한다.

지형은 세 종류의 칸으로 이루어진 2차원 격자다.

• P — (마른) 초목이 있는 칸.
• . — 초목이 없는 칸.
• F — 불이 시작되는 칸. 이런 칸은 적어도 하나 존재한다.

시간 $0$에 모든 F 칸에서 불이 시작된다. 불이 붙은 칸에서 불꽃이 다른 초목 칸 또는 불 칸으로 튈 수 있다. 두 칸 사이의 직선(유클리드) 거리 $d$를 튀는 불꽃은 도착하기까지 $d^2$ 만큼의 시간이 걸린다.

비용이 거리의 제곱으로 커지므로, 한 번에 멀리 튀는 것보다 짧게 여러 번 튀는 편이 빠르다. 거리 $d$를 한 칸씩 이동하면 비용이 $d$뿐이지만, 한 번에 거리 $d$를 튀면 $d^2$이 든다. 그래서 불은 빽빽한 초목 사이는 빠르게 번지지만, 넓게 빈 곳에서는 불꽃이 운 좋게 멀리 날아가야 하므로 느려진다. . 칸에는 초목이 없어 절대 타지 않는다.

각 지형에 대해, .이 아닌 모든 칸이 불타는 가장 이른 시각을 구하라.

첫째 줄에 데이터 집합의 수 $K$가 주어진다. 각 데이터 집합은 다음과 같은 형식이다.

• 두 정수 $h$와 $w$ ($1 \le h, w \le 20$)가 있는 줄. 각각 지도의 높이와 너비다.
• 이어서 $h$개의 줄이 주어지며, 각 줄은 정확히 $w$개의 문자로 이루어진다. 각 문자는 P, F, . 중 하나다.

각 데이터 집합에 대해 Data Set x: 줄을 출력한다. 여기서 $x$는 데이터 집합의 번호(1부터 시작)다. 다음 줄에 .이 아닌 모든 칸이 불타는 가장 이른 시각을 출력한다. 데이터 집합 사이에는 빈 줄을 하나 출력한다.