여행하는 퀸

흑이 패배하고 백의 군대가 승리했지만, 안타깝게도 백의 킹이 전투에서 전사했습니다. 그래서 백의 퀸은 새로운 짝을 찾고 있습니다. 어느 나이트와 결혼할지 정하지 못한 퀸은 모든 나이트를 한 번씩 찾아가 보기로 했고, 그런 다음 마지막으로 비숍을 만나 결혼을 준비하려고 합니다.

체스판의 현재 상황이 주어질 때, 퀸이 모든 나이트를 방문하고 마지막에 비숍을 방문하기까지 필요한 최소 이동 횟수를 구하세요.

퀸은 어떤 말을 “방문”할 때 그 말과 인접한 (최대 여덟 개의) 칸 중 하나에 서 있기만 하면 됩니다. 두 번의 방문 사이에 반드시 이동해야 하는 것은 아니며, 한 칸에서 인접한 여러 말을 동시에 방문할 수 있습니다. 한 번의 이동에서 퀸은 여덟 방향(가로, 세로, 대각선) 중 하나로 원하는 만큼 여러 칸을 갈 수 있습니다. 단, 비어 있지 않은 칸을 지나가거나 그 칸에 멈출 수는 없습니다.

첫 번째 줄에는 시나리오의 개수가 주어집니다. 각 시나리오는 하나의 체스판 상태로 이루어지며, 랭크 8, …, 1 순서대로 한 줄에 한 랭크씩 주어집니다. 각 줄은 그 랭크의 a열부터 h열까지 여덟 칸을 나타내는 8개의 문자로 이루어집니다. 각 체스판 설명 뒤에는 빈 줄이 올 수 있습니다.

Q는 퀸의 시작 위치를, B는 비숍이 서 있는 칸을 나타내며 각각 정확히 하나씩 있습니다. P로 표시되는 폰은 임의의 개수만큼 있을 수 있고 이동을 가로막기만 합니다. N으로 표시되는 나이트는 2개에서 14개까지 있습니다. 그 밖의 모든 칸은 .(빈 칸)으로 주어집니다.

각 시나리오에 대해 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 i는 1부터 시작하는 시나리오 번호입니다.

그 다음 줄에는, 이동 횟수가 최소이면서 마지막 칸이 비숍과 인접하고 모든 나이트를 한 번 이상 방문하는 경로들 중 사전순으로 가장 앞선 경로를 출력합니다. 경로는 퀸이 서는 칸들의 이름을 순서대로 이어 붙여 한 줄로 나타내며, 시작 칸도 포함합니다. 각 칸의 이름은 소문자 열 문자(a–h) 하나와 행 숫자(1–8) 하나로 이루어집니다. 그러한 경로가 존재하지 않으면 impossible을 한 줄에 출력합니다. 연속한 두 시나리오 사이는 빈 줄로 구분합니다.