2919：Traveling Queen Problem

The first line contains the number of scenarios. Each scenario consists of a chessboard description. The rows 8, …, 1 are given in this order, one line per row. Each line contains 8 characters to represent the squares at columns a, …, h of this row. Each description is followed by an empty line.

There is one character Q to denote the starting position of the queen, and one B to denote the square on which the bishop stands. There is an arbitrary number of pawns, given as P, who simply block movement, as well as 2–14 knights denoted as N. All other squares are given as ‘.’ and are empty.

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1.

Then print the lexicographical first path that contains the minimal number of moves, ends adjacent to the bishop and visits each knight at least once. The path shall be given on a single line by concatenating in order the names of the squares on which the queen stands. Each square name consists of a small letter followed by a decimal digit. If no such path exists, output “impossible” on a single line. Terminate the output for the scenario with a blank line.