N-퍼즐은 많은 다양한 형태와 이름이 있다. 이번 문제에서 우리가 살펴볼 것은 15-퍼즐이다.

15-퍼즐은 4*4보드에서 움직일 수 있는 정사각형으로 이루어져 있고, 한 정사각형은 빠져있다. 정사각형은 A부터 O까지 이름이 붙여져 있다. 이 퍼즐을 풀면 다음과 같은 그림이 된다.

우리는 이러한 15-퍼즐에서 흩어짐 정도를 계산할 수 있다. 흩어짐 정도는 각 정사각형의 현재 위치와 퍼즐을 풀었을 때의 위치와의 거리의 합이다.

두 정사각형의 거리는 그 두 정사각형 사이의 맨해튼 거리이다.

15-퍼즐이 주어졌을 때, 흩어짐 정도를 계산하는 프로그램을 작성하시오.

입력 형식

4줄에 걸쳐 현재 퍼즐의 상태가 주어진다.

출력 형식

퍼즐의 흩어짐 정도를 출력한다.

예제 입력 1

ABCD
EFGH
IJKL
M.NO

예제 출력 1

2

예제 입력 2

.BCD
EAGH
IJFL
MNOK

예제 출력 2

6