This is an interesting game consisting of eight blocks in a nine-position-square with an empty position. There is a beautiful picture broken into eight pieces with each pressed in one block. But initially, pieces of picture are ordered randomly. By moving a block up, down, left, or right to the empty place, you can make the picture recovered.
Now we use uppercase characters to denote small pieces. For example, the left diagram below denotes the initial configuration the right one below denotes the end configuration:
By moving ¡®G' left, ¡®H' down, ¡®E' left, ¡®F' up, you can make it recovered by 4 operations totally. So, giving the initial and the end configuration, please give least operations needed to recover the picture.
There are multiple test cases. Each test case consists of an initial and an end configuration, each consisting of 8 distinct uppercase characters and ¡®@' specify the empty place. There is an empty line between two test cases.
Output the minimum operation needed to recover the picture. If there is no solution, print -1.
ABC DHE @GF ABC DEF GH@Sample output
BKG FP@ CDY FBK GPD CY@