좌회전 금지

• 세 머리 모두: 원탁의 기사라고?
• 로빈: 그렇소.
• 왼쪽 머리: 그렇다면 내가 자네를 죽여야겠군.
• 가운데 머리: 그래야 하나?
• 오른쪽 머리: 글쎄, 난 아닌 것 같은데.
• 가운데 머리: 그럼 난 뭐라고 생각하지?
• 왼쪽 머리: 죽이자고.
• 오른쪽 머리: 그러지 말고 잘 대해 주자니까.
• 가운데 머리: 아, 좀 조용히 해.

머리 셋이 옥신각신하는 사이에 기사는 달아났다. 오른쪽 머리는 자기가 나서서 성터를 뒤지기로 했다. 기사를 찾으면 왼쪽 머리, 가운데 머리와 함께 그를 해치우고 차와 비스킷을 먹을 참이다.

아래 $8 \times 12$ 미로를 보자. 회색으로 칠한 칸은 벽이라서 들어갈 수 없다.

오른쪽 머리(출발점 S)와 기사(도착점 F) 사이의 최단 경로는 그림처럼 길이가 3이다. 그런데 오른쪽 머리는 좌회전도 U턴도 하지 못한다. 앞으로 가거나 오른쪽으로 도는 것만 된다. 그래서 오른쪽 머리가 찾을 수 있는 가장 짧은 경로는 훨씬 길어져서 29가 된다.

한 번 움직일 때 오른쪽 머리는 바로 앞 칸이나 바로 오른쪽 칸으로 들어가고, 들어간 방향을 새로 바라본다. 첫 이동만은 동서남북 어느 쪽으로든 할 수 있다. 경로의 길이는 이렇게 움직인 칸 수다.

첫 줄에 미로의 개수 $N$($N > 0$)이 주어진다. 이어서 미로마다 첫 줄에 행의 수 $r$($3 < r \le 20$)와 열의 수 $c$($3 < c \le 20$)가 공백을 사이에 두고 주어지고, 그다음 $r$개 줄에 각각 $c$개의 문자가 주어져 미로를 나타낸다.

X는 벽이라서 들어갈 수 없는 칸, S는 출발 칸, F는 기사가 있는 칸이고, 공백은 자유롭게 지나갈 수 있는 칸이다.

미로마다 오른쪽 머리가 출발 칸에서 도착 칸까지 갈 수 있는 가장 짧은 경로의 길이를 한 줄에 하나씩 출력한다.

• 오른쪽 머리는 출발 칸에서 동서남북 어느 방향으로든 첫 걸음을 뗄 수 있다. 그다음부터는 앞으로 가거나 오른쪽으로 도는 것만 할 수 있다.
• 출발 칸과 도착 칸은 절대 같지 않다.
• 미로는 항상 사방이 벽으로 둘러싸여 있다.
• 출발 칸과 도착 칸 사이에는 오른쪽 머리가 실제로 지나갈 수 있는 경로가 항상 있다고 가정해도 된다.