캔디콘의 아이들

옥수수밭 미로는 인기 있는 핼러윈 놀이 시설이다. 방문객은 입구로 들어가 미로 속을 헤매다가 출구를 찾아 나온다.

미로를 반드시 빠져나올 수 있는 잘 알려진 방법이 하나 있다. 한쪽 손(왼손 또는 오른손)을 벽에 대고, 그 손을 절대 떼지 않은 채 같은 벽을 계속 따라가는 것이다. 왼쪽과 오른쪽 중 어느 쪽이 항상 더 유리한지는 정해져 있지 않으며, 이렇게 따라간 경로가 가장 짧은 경로인 경우도 드물다. (이 방법은 출구가 바깥 테두리에 있지 않은 미로에서는 통하지 않지만, 그런 미로는 이 문제에 나오지 않는다.)

곧 미로로 꾸며질 옥수수밭의 주인인 당신은, 주어진 미로에 대해 왼손 경로의 길이, 오른손 경로의 길이, 그리고 최단 경로의 길이를 계산해 주는 프로그램을 원한다. 이를 통해 어떤 배치가 방문객을 가장 헷갈리게 만드는지 판단할 수 있다.

벽을 따라갈 때는 항상 상하좌우로 인접한 빈 칸으로만 이동하며, 대각선 이동은 허용되지 않는다. 출발은 입구에서 미로 안쪽을 향해 시작하고, 출구에 도착하는 즉시 멈춘다.

첫 번째 줄에는 미로의 개수 $n$이 주어진다.

각 미로는 너비 $w$와 높이 $h$ ($3 \le w, h \le 40$)가 적힌 줄로 시작하고, 이어서 각 줄이 정확히 $w$개의 문자로 이루어진 $h$개의 줄이 미로 배치를 나타낸다.

• # 는 벽,
• . 는 빈 칸,
• S 는 출발점(입구),
• E 는 출구를 뜻한다.

각 미로에는 S와 E가 정확히 하나씩 있다. 둘은 모두 미로의 바깥 테두리에 있지만 모서리(코너)에는 놓이지 않으며, 적어도 하나의 벽으로 서로 떨어져 있다. 미로는 벽으로 완전히 둘러싸여 있고, S와 E만이 유일한 통로이다. 출구는 항상 출발점에서 도달할 수 있다.

각 미로마다 한 줄에 세 정수를 공백 하나로 구분하여 출력한다. 왼손 경로, 오른손 경로, 최단 경로가 각각 지나는 칸의 개수이며(S와 E를 포함하고, 같은 칸을 여러 번 지나면 그만큼 여러 번 센다), 이 순서로 출력한다. 이동은 상하좌우로만 가능하고 대각선 이동은 허용되지 않는다.