Traveling Queen

Black has been defeated and the white army has won, but unfortunately the white king was killed in the fight, so the white queen is looking for a new mate. Unsure which of the knights to marry, she has decided to visit them all, and afterwards to see the bishop to arrange the marriage.

Given the current situation on a chessboard, find the smallest number of moves in which the queen can visit every knight and, finally, visit the bishop.

The queen visits a piece by standing on one of the (at most) eight squares adjacent to it; she does not necessarily have to move between two visits, and several pieces may be visited from the same square. In a single move the queen may travel any number of squares in one of the eight directions (horizontal, vertical, or diagonal). No move may pass through or stop on a non-empty square.

The first line contains the number of scenarios. Each scenario is a chessboard description: ranks 8, …, 1 are given in that order, one line per rank. Each line has 8 characters describing columns a, …, h of that rank. A description may be followed by a blank line.

Exactly one square holds Q, the starting position of the queen, and exactly one holds B, the square on which the bishop stands. Any number of pawns may be present as P; they only block movement. Between 2 and 14 knights are present as N. Every other square is . and is empty.

For each scenario, first print a line Scenario #i:, where i is the scenario number starting at 1.

On the following line print, among all paths that use the minimum number of moves, end on a square adjacent to the bishop, and visit every knight at least once, the lexicographically first one. The path is written on a single line by concatenating, in order, the names of the squares on which the queen stands (including her starting square). Each square name is a lowercase column letter (a–h) followed by a row digit (1–8). If no such path exists, print impossible on its own line. Separate consecutive scenarios with a blank line.