Jammed
The classic game 15 involves arranging tiles numbered from 1 to 15 within a 4×4 grid. Inspired by this, a new version has been created using a 4×2 grid with 7 tiles. In this version, the tiles are marked with letters from the Latin alphabet and Arabic numerals (each tile has one symbol, but different tiles may share the same symbol). The goal is to rearrange the initial configuration of tiles to match a specified pattern in the fewest possible moves.
The empty space is denoted by the symbol # and is used to shift tiles around the grid. Tiles can be moved into the empty space from adjacent cells that share a common edge. For example, in the illustration, the rightmost symbol 0 can be moved down into the empty space, placing 0 in the lower cell and leaving the upper cell empty. Similarly, the letter C or the number 2 can be moved into the empty space.
Input
The first line contains the number of test cases (up to 100). Each test case consists of four lines: the first two lines represent the initial arrangement of symbols, and the next two lines represent the target pattern. Each line contains 4 symbols (Latin letters and Arabic numerals), with the empty space indicated by the symbol #. Test cases are separated by an empty line.
Output
For each test case, output a line with the minimum number of moves needed to reach the target arrangement. If the target arrangement is not achievable, output -1.