화재 대피 계획

맑은 날, 오렌지랜드의 많은 사람들이 직사각형 모양의 꽃 정원을 구경하고 있다. 갑자기 화재 경보가 울리자 모두가 혼란에 빠지고, 각자 하나뿐인 출구로 최대한 빨리 대피하려 한다. 이때 사람들은 (방화 유리 상자에 담긴) 꽃을 밟거나 다른 사람과 부딪히지 않도록 조심한다. 이 예의 바른 방문객들을 위한 최적의 대피 계획을 구하라.

정원은 직사각형 격자로 표현된다. 각 칸에는 꽃이 있거나, 사람이 서 있을 수 있는 빈 공간이 있다. 한 칸에서 상하좌우로 인접한 칸으로 이동하는 데 정확히 1초가 걸린다. 이 이동은 다음 순간에 도착 칸에 꽃이 없고 다른 사람도 없을 때에만 가능하다. 특히 두 사람이 같은 칸에 동시에 들어가려 한다면, 계획은 그중 한 명만 들어가게 해야 하며 나머지 한 명은 (이동할 다른 칸이 없는 한) 기다려야 한다.

정원 전체를 대피시키는 데, 즉 모든 사람이 출구에 도달할 때까지 필요한 최소 시간(초)을 구하라. 모든 사람은 시작 칸에서 출구까지 꽃을 피해 갈 수 있는 경로가 적어도 하나 존재함이 보장된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$ ($3 \le n, m \le 100$)이 주어진다. 정원은 $n$개의 행과 $m$개의 열로 이루어지며, 각 칸의 크기는 $1 \times 1$이다. 이어지는 $n$개의 줄에는 각각 $m$개의 문자가 주어지며, 화재 경보가 울린 순간의 정원 상태를 나타낸다. 각 문자는 #, F, P, -, * 중 하나이다.

• # : 정원의 경계
• * : 출구. 정확히 하나 존재하며, 경계 위의 # 자리에 놓인다.
• F : 꽃이 있는 칸
• P : 사람이 있는 칸
• - : 빈 칸

입력의 끝은 0 0으로 이루어진 줄로 표시되며, 이 줄은 어떤 테스트 케이스에도 포함되지 않는다.

각 테스트 케이스마다 정원을 대피시키는 데 필요한 최소 시간(초)을 한 줄에 하나씩 출력한다.