Computer Science is so hard these days that students in a senior design group have decided to work on a project to have drones fly them dinner while they are hard at work on their coursework. Naturally, the senior design group would like to offer this feature for multiple groups of people,

each of who may be located in different places and might want food from different places.

The group did a great job with their drone design. It flawlessly picked up food and could fly that

food to the appropriate location. Unfortunately, they only built one remote control for the $($upto$)$

four drones to deliver food. That means that even if best path for two drones is different, the drones

are limited to moving in the same direction each time. Of course, if this were always true, then the

drones would rarely be able to complete all of their deliveries. Luckily, however, some areas of

the sky are marked as $$no$-$fly zones.$$ Thus, if a drone is directed to move into one of these no$-$fly

zones, instead of moving, it will stay put. This means that with just one controller, different drones

might end up moving different paths. Also, once a drone successfully delivers food to its senior

design group, it will ignore all future commands and stay put.

We can model the map the drones will be navigating as an $8$ by $8$ grid, where some squares are

marked as no$-$fly zones, some squares are the starting spots for the drones $($this is the restaurant

from which they pick up food$),$ and some squares are the locations of the senior design groups:

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_$ G$3$

$\_\_\_\_$ D$2\_\_$ D$1\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ XX XX

$\_\_\_\_\_\_\_\_$ G$1\_\_\_\_\_\_$

$\_\_\_\_$ G$2\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ D$3\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ XX $\_\_$

In the grid above, there are three drones delivering meals to three senior design groups. The drones

are numbered D$1$ through D$3$ and the senior design groups are numbered G$1$ through G$3.$ The

drone Dx is delivering food to the group Gx$.$

The remove control allows the drones to move north $($up$),$ south $($down$),$ east $($right$)$ and west $($left$),$

a single grid square. For example, if we hit the down button twice, the new state of our grid is

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_$ G$3$

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ XX XX

$\_\_\_\_$ D$2\_\_$ A$1\_\_\_\_\_\_$

$\_\_\_\_$ G$2\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ D$3\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ XX $\_\_$

$2$

After two moves, the first drone has successfully delivered its food. $($This is denoted by A$1$ for

arriving above.$)$ The second drone has also moved down two squares and is one square away from

its destination. The third drone has moved down only one square because when the remote told it

to go down the second time, the third drone saw that the square below was a no$-$fly zone.

After a third move down, the second drove delivers its food:

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_$ G$3$

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ XX XX

$\_\_\_\_\_\_\_\_$ A$1\_\_\_\_\_\_$

$\_\_\_\_$ A$2\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ D$3\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_$ XX $\_\_$

From here, the shortest route for the third drove to deliver its food takes $9$ moves. $($One such

sequence is up$,$ up$,$ up$,$ left, up$,$ up$,$ up$,$ right, right.$)$ In total using this set of button presses, it takes

$12$ button presses to get all three drones to successfully deliver its food.

Some other notes:

$1)$ The entire $8$ by $8$ grid is surrounded by no$-$fly zone squares $($not drawn in but just assumed to

be there.$)$

$2)$ Two drones may occupy the same grid square at the same time so long as it$$s not a no$-$fly zone

square.

$3)$ A drone treats each group$$s location except for the one it$$s delivering to as a no$-$fly zone. It

would be unfair to tempt students in the wrong group with food and then just fly through.

The Problem:

Given the initial state of the $8$ by $8$ grid, showing the initial locations of the drones, the locations

each of the drones must deliver their food and the no$-$fly zone squares, determine the fewest

number of remote control button presses necessary to have all of the drones successfully deliver

their food. If this is impossible, determine that the task is not possible.

The Input:

The first line of input contains a single integer, n $(1<=$ n $<=4),$ representing the number of drones

for the input case. The corresponding drones are labeled D$1$ through Dn and the corresponding

groups to which they are delivering food are labeled G$1$ through Dn$.$

The following eight lines each contain $8$ space separated strings of two characters each,

representing that row of the input grid. If the two characters are $\_\_,$ the grid square is an open

square. If the two characters are $$Dk$$ where k is a digit in between $1$ and n$,$ then that represents

drone k$$s starting position. If the two characters are $$Gk$$ where k is a digit in between $1$ and n$,$

$3$

then that represents the destination drone k is delivering food. Finally, if the two characters are

$$XX$,$ that means the co