워레즈 테스트

지미는 크리스틴과 결혼하고 싶어 한다. 크리스틴은 마을의 거의 모든 창고를 소유한 워레즈 씨의 딸이다. 워레즈 씨는 자기 밑에서 일하는 사람에게만 딸을 시집보내려 하고, 창고에서 상자를 제대로 밀 줄 모르면 애초에 그의 밑에서 일할 수조차 없다. 그래서 지미는 먼저 그 유명한 "워레즈 테스트"를 통과해야 한다.

각 지도는 창고의 구조를 정사각형 칸들의 격자로 나타낸다. 모든 칸은 벽이거나, 상자 하나가 놓여 있거나, 비어 있다. 일부 칸은 목표 칸으로 표시되어 있고, 정확히 한 칸이 지미의 시작 위치이다.

지미는 한 번에 한 칸씩 북(위), 서(왼쪽), 동(오른쪽), 남(아래) 네 방향 중 하나로 움직인다. 지미는 빈 칸으로 들어갈 수 있고, 상자가 놓인 칸으로도 들어갈 수 있는데, 이때는 그 상자를 같은 방향으로 한 칸 더 밀 수 있어야 한다. 즉 상자 바로 너머의 칸이 비어 있어야 한다. 벽 칸은 결코 비어 있지 않다. 따라서 한 번의 이동으로 밀리는 상자는 많아야 하나이며, 그 상자는 정확히 한 칸만 움직인다. 지미는 상자를 벽이나 다른 상자 쪽으로 밀 수 없다.

모든 지도의 첫 행과 마지막 행, 첫 열과 마지막 열은 항상 벽이다. 모든 지도에서 상자의 개수는 목표 칸의 개수와 같으며, 상자는 항상 적어도 하나 있다. 지미는 마지막에 모든 상자가 목표 칸 위에 놓이도록 움직여야 한다. 해의 길이는 지미가 움직인 횟수이며, 그 움직임이 상자를 밀었는지 여부는 상관없다. 움직임 횟수가 가장 적은 해를 구하여라. 모든 지도에는 해가 적어도 하나 존재한다.

첫 줄에 시나리오(지도)의 개수가 주어진다.

각 지도에 대해, 첫 줄에는 지도의 행 수와 열 수(둘 다 15 이하)가 공백으로 구분되어 주어진다. 이어지는 줄들에 지도가 한 줄에 한 행씩 주어지며, 'X'는 벽, 'T'는 목표 칸, '.'는 빈 칸을 나타낸다.

그 다음 줄에는 지미의 시작 위치가 행과 열의 순서로 공백으로 구분되어 주어진다. 그 다음 줄에는 상자의 개수가 주어진다. 이어지는 각 줄에는 상자 하나의 시작 위치가 행과 열의 순서로 공백으로 구분되어 주어진다.

행과 열의 번호는 왼쪽 위 모서리를 0으로 하여 매긴다.

각 시나리오에 대해, 먼저 "Scenario #i:" 형태의 줄을 출력한다. 여기서 i는 1부터 시작하는 시나리오 번호이다. 다음 줄에는 가장 짧은 해에서 지미가 움직인 순서를 출력한다. 북(위)은 'n', 서(왼쪽)는 'w', 동(오른쪽)은 'e', 남(아래)은 's'로 나타낸다. 움직임 횟수가 가장 적은 해가 여럿이라면, 문자열을 한 글자씩 비교했을 때 사전순으로 가장 앞서는 것(글자 순서는 e < n < s < w)을 출력한다. 움직임이 필요 없으면 빈 줄을 출력한다. 서로 이웃한 두 시나리오의 출력 사이에는 빈 줄을 하나 출력한다.