칸 외판원

프로젝트 오일러 문제를 전부 머릿속으로 풀었으니, 이제 결정 버전이 NP-완전인 고전 문제, 외판원 순회를 볼 차례다.

이 문제의 무대는 직사각형 격자다. 한 번의 이동은 지금 있는 칸과 변을 맞댄 칸으로 가는 것이고, 따라서 각 칸은 위, 아래, 왼쪽, 오른쪽 칸과 이어져 있다. 같은 칸에는 원하는 만큼 여러 번 들어갈 수 있다. 물론 대부분의 칸은 두 번 볼 만큼 재미있지 않다.

정확히 한 칸에 S가 적혀 있다. S에서 출발해 격자의 모든 칸을 적어도 한 번 밟고 다시 S로 돌아온다. 이런 왕복에 필요한 최소 이동 횟수를 구한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 격자의 너비 $X$와 높이 $Y$가 주어진다. 이어서 $X$개의 문자로 이루어진 줄이 $Y$개 주어진다. 문자 C는 평범한 칸이고, 문자 S는 출발점이다.

• $0 < T \le 50$
• $0 < X \le 100$
• $0 < Y \le 100$
• 한 테스트 케이스에서 문자 하나만 S이고 나머지는 모두 C다.

각 테스트 케이스마다 S에서 출발해 모든 칸을 적어도 한 번 방문하고 S로 돌아오는 왕복의 최소 이동 횟수를 한 줄에 출력한다.

이래 봐야 아무 데도 이르지 못한다는 것을 이미 알고 있으니, 마지막 테스트 케이스 뒤에 LOL만 적힌 줄을 출력한다. 테스트 케이스마다가 아니라 실행 한 번에 한 줄만 출력한다.