Description

On a $4\times 4$ chessboard, there are $8$ black pieces and $8$ white pieces. Two pieces are considered adjacent if and only if their respective squares share a common edge. The rule for moving a piece is to swap two adjacent pieces.
Given an initial chessboard and a target chessboard, find the shortest sequence of moves that transforms the initial chessboard into the target chessboard.

Input Format

The first four lines, each containing $4$ numbers (either $1$ or $0$), describe the initial chessboard;
This is followed by a blank line;
The sixth to ninth lines, each containing $4$ numbers (either $1$ or $0$), describe the target chessboard.

Output Format

The first line of the output file should be an integer $n$, representing the minimum number of moves required.

Sample 1

1111
0000
1110
0010

1010
0101
1010
0101

4