Jammed#412
Everyone is familiar with the game 15, where the goal is to arrange an initially random sequence of numbers by moving tiles numbered from to on a 4 \times 4 grid. Based on this, another game has been designed: in this game, the field consists of a 4 \times 2 grid with tiles, and the tiles are marked with Latin letters or Arabic numerals (each tile has one symbol, but different tiles may bear the same symbol). The objective remains the same—arrange the starting configuration to match a target pattern in the minimum number of moves.
The empty cell is denoted by the special symbol # and is used to move tiles around the grid. A tile may only be moved into the empty cell from an adjacent cell sharing a common edge. For example, in the illustration, the rightmost symbol can be moved downward into the empty cell, placing in the lower cell and making the upper cell empty, or the symbol C or the digit can be moved into the empty cell.
The first line contains the number of test cases (no more than ). Each test consists of four lines: the first two lines indicate the initial configuration, and the next two lines represent the target pattern. Each line has symbols (Latin letters and Arabic numerals), with the empty cell indicated by #. The tests are separated by an empty line.
For each test, output a line containing the minimum number of moves required to reach the target configuration. If it is not possible to obtain the required configuration, print -1.
Example 1