ASCII Labyrinth

A board of size m x n contains one 1 x 1 piece in each square. Each piece has one of three patterns, and a piece may be rotated only inside its own square; it may not be moved to another square.

The piece types are:

• Blank piece: contains no line and cannot be part of a route.
• Straight piece: its middle row is drawn as ***, as shown below, and after rotation it connects two opposite edges.

   ***   

• Corner piece: drawn as below, connects two adjacent edges, and may be rotated in any of the four directions.

   **  * 

Given the initial board, decide whether the pieces can be rotated to form at least one polygonal route that starts at some edge of the upper-left square and ends at some edge of the lower-right square. A route cannot use a blank piece and cannot use the same square twice.

The first line contains an integer c, the number of test cases.

Each test case starts with two integers m and n, the number of rows and columns. The next 4m + 1 lines contain an ASCII drawing of the current board. The drawing uses the characters +, -, |, *, and spaces.

Every board satisfies m x n <= 64.

For each test case, if a desired route can be formed, first print one route using the fewest possible number of squares, in the same grid format as the input. If there are several such shortest routes, any one may be printed. Squares not used by the route must be blank.

Then print Number of solutions: X, where X is the number of different valid routes. If no route can be formed, do not print a board; print only this line.