Knights' Journey

Changhyeon and Yehwan became interested in chess recently and decided to buy a square chessboard of 4 rows and 4 columns, with 4×4 cells. However, Changhyeon chose the wrong purchase option and bought a board filled only with knights! A knight, one of the chess pieces, moves once by going two cells in one of the four directions (up, down, left, or right) from its current position, then turning to a direction perpendicular to it and going one more cell. After a knight moves, it must not leave the board, and no two or more knights may be on the same cell.

Wondering what to do with the wrong board, Changhyeon and Yehwan drew two boards, A and B, each with knights placed on it. They agreed that whoever computes the minimum number of moves needed to turn the knights on A into the arrangement of B more slowly will clean up the board. Changhyeon does not want to clean up, so he is determined to win.

Help Changhyeon by writing a program that computes the minimum number of knight moves. Only one knight can move at a time.

Rows 1 to 4 give board A, and rows 5 to 8 give board B. A 0 means an empty cell, and a 1 means a cell with a knight. Each of boards A and B contains at least one knight, and the input always has a solution.

Print the minimum number of knight moves needed to change the knights on board A into the arrangement of board B.