점심 약속

캠퍼스에는 맛있는 점심 식당이 많습니다. 식사하기 전에 여러분과 친구들은 먼저 한 곳의 약속 장소에 모인 뒤, 다 함께 식당으로 걸어갑니다. 모두가 걷는 거리의 총합이 가장 짧아지도록 약속 장소와 식당을 골라야 합니다.

캠퍼스 지도가 주어집니다. 어떤 칸은 약속 장소, 어떤 칸은 식당으로 표시되어 있고, 여러분과 각 친구가 출발하는 칸도 주어집니다. 약속 장소와 식당을 하나씩 정하면, 각 사람은 자기 출발 칸에서 약속 장소로, 거기서 다시 식당으로 걸어간 뒤, 마지막으로 자기 출발 칸으로 돌아옵니다.

가능한 모든 선택 중에서, 모든 사람이 걷는 거리의 합이 최소가 되는 (약속 장소, 식당) 쌍을 고르세요. 이동은 인접한 칸으로 상하좌우로만 할 수 있으며, 대각선 이동은 불가능합니다.

첫 줄에 데이터 집합의 개수 $K \ge 1$ 이 주어집니다. 이어서 각 데이터 집합이 다음 형식으로 주어집니다.

각 데이터 집합의 첫 줄에는 지도의 높이 $h$ 와 너비 $w$ 가 주어집니다 ($1 \le h, w \le 30$). 그다음 $h$ 개의 줄에는 각각 $w$ 개의 문자가 있으며, 각 문자는 다음 중 하나입니다.

• X — 지나갈 수 없는 칸 (건물, 울타리 등).
• . — 지나갈 수 있는 칸.
• R — 식당. 식당을 통과해서 지나갈 수는 없지만, 인접한 지나갈 수 있는 칸에서 식당으로 들어가거나 식당에서 그 칸으로 나올 수는 있습니다.
• M — 약속 장소. 통과해서 지나갈 수 있습니다.
• S — 여러분 또는 친구 한 명의 출발 칸. 통과해서 지나갈 수 있습니다.

이동은 상하좌우로만 가능하며 대각선으로는 이동할 수 없습니다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 $x$ 는 데이터 집합의 번호입니다 (1부터 시작). 다음 줄에는 약속 장소와 식당을 가장 좋은 하나의 쌍으로 골랐을 때, 여러분과 모든 친구가 걷는 거리의 총합의 최솟값을 출력합니다. 경로를 출력할 필요는 없습니다.

모든 출발 칸에서 도달할 수 있는 약속 장소가 없거나, 그러한 식당이 없다면, 숫자 대신 Impossible 을 출력합니다.