Detective Junha

Detective Junha is asked to find the thief behind a run of art thefts. Several museums lost works one after another. Junha painted for a living years ago, took the news badly, and agreed to work the case at once.

The area where the thefts happened is drawn as a grid with 4 rows and 5 columns. The clues gathered so far are the cell where the thief started, the cells of the robbed museums together with the order of the thefts, and the cells where traces of the thief were found. Junha put a mathematical mind and an eye for art to work and settled on these rules for the thief.

• The thief moves one cell at a time, up, down, left, or right. The thief never leaves the grid.
• On reaching a museum that has not been entered yet, the thief walks in and steals the work right away. Museums are therefore entered in the order the thefts happened. Moving onto the cell of museum 2 or museum 3 before visiting museum 1 is impossible.
• Every cell the thief walked on keeps a trace. A cell with no trace was never walked on, and a cell where a trace was found was walked on at least once. The thief can walk on the same cell several times.

Help Junha and find the shortest distance the thief moved.

The input holds several test cases. The first line has the number of test cases $T$ ($1 \le T \le 10$).

Each test case is 4 lines, and each line is a string of length 5. The characters mean:

• 0: the cell where the thief started.
• a number from 1 up: a robbed museum cell, where the number is the order of the theft. A number larger than 9 is written as an uppercase letter starting at A, so 10 is A and 11 is B.
• #: a cell where a trace of the thief was found.
• .: a cell with no relation to the case.

0 appears exactly once. The museum numbers run from 1 upward with no gaps, and no number appears twice. The grid holds 20 cells, so there are at most 19 museums and the largest label is J. A blank line separates consecutive test cases.

For each test case, print the shortest distance the thief moved, one per line. The distance is the number of times the thief stepped from one cell to another, so a thief that never moved from the starting cell gives 0.

The thief has to walk at least once on every cell that is not ., that is the starting cell, every museum cell, and every cell holding a trace. A cell already walked on can be walked on any number of times again, but museums have to be entered for the first time in the order the thefts happened.

If no route satisfies the rules, print -1.