늪지대 캥거루

캥거루는 흥미로운 동물이다. 우선 새끼를 주머니에 넣어 다니는 모습이 무척 귀엽고, 우리가 아기를 안고 다니는 방식을 떠올리게 한다. 또한 캥거루는 아주 멀리 뛸 수 있는데, 이는 물 위에 착지하고 싶지 않은 상황 — 예를 들어 작은 땅 조각들만 있고 악어가 헤엄쳐 다니는 늪에 갇힌 캥거루에게 — 매우 유용하다. 순수한 도약 능력뿐 아니라, 그 능력을 어떻게 써서 목적지에 도달할지 계산하는 능력도 도움이 된다. 바로 이때 프로그래밍을 하는 친구들이 나설 차례다.

캥거루의 이동은 다음과 같이 모형화한다. 캥거루는 남–북 또는 동–서 방향으로만 이동할 수 있으며, 대각선 같은 다른 방향으로는 이동할 수 없다. 한 번의 도약에서 캥거루는 $1$ 이상 $5$ 이하의 정수 거리만큼 뛸 수 있고, 한 번의 도약은 시간 $1$이 걸린다. 다만 긴 도약 뒤에는 다시 뛰기 전에 쉬어야 한다. 거리 $d$만큼 뛴 뒤에는 다음 도약을 하기 전에 $(d-1)^2$의 시간만큼 쉬어야 한다. 또한 다음 도약의 방향이 직전 도약의 방향과 다르면, 방향을 바꾸기 위해 두 도약 사이에 시간 $1$이 추가로 든다.

늪은 2차원 격자로 주어진다. 각 칸은 물이거나(점 .으로 표시) 땅이다(X로 표시). 두 칸은 특별히 표시되어 있는데, K는 캥거루의 시작 위치, G는 도달하려는 목표 지점이다(둘 다 당연히 땅이다). 도약은 물 위를 지나갈 수 있지만, 캥거루는 반드시 격자 안의 땅 칸에 착지해야 한다. 캥거루가 목표에 도달할 수 있다면 그 최소 시간을 구하라. 도착했을 때 지쳐 있어도 상관없으며, 도착한 뒤에는 쉬지 않아도 된다.

첫 줄에 데이터 집합의 수 $K$가 주어진다. 이어지는 각 데이터 집합은 다음과 같은 형식이다. 첫 줄에 늪 지도의 높이와 너비를 나타내는 두 정수 $h$, $w$ ($1 \le h, w \le 30$)가 주어진다. 다음 $h$개의 줄에는 각각 정확히 $w$개의 문자가 있으며, 각 문자는 ., X, K, G 중 하나이다. 이 $h \times w$개의 문자가 늪을 나타낸다. 각 데이터 집합에는 K와 G가 각각 정확히 하나씩 있다.

각 데이터 집합에 대해 한 줄에 Data Set x:를 출력한다. 여기서 x는 그 데이터 집합의 번호이다($1$부터 시작). 다음 줄에는 캥거루가 목표에 도달하는 최소 시간을 출력하고, 도달할 수 없으면 대신 Impossible을 출력한다. 서로 인접한 데이터 집합 사이에는 빈 줄을 하나 출력한다.