점 잇기

종이 위의 점 9개를 연필을 떼지 않고 선분 4개로 모두 잇는 퍼즐은 잘 알려져 있다. 시모네는 이 퍼즐을 일반화한 "점 잇기"라는 게임을 만들었다.

점 잇기에서는 행 간격과 열 간격이 같은 4 × 4 격자 위에 점이 놓여 있다. 각 점에는 1부터 16까지의 번호가 하나씩 겹치지 않게 적혀 있다. 점 1에서 시작해 점 16에서 끝나도록 번호 순서대로 점을 이어야 한다.

연필은 종이에서 떼지 않고 직선 선분을 이어서 그린다. 첫 선분은 점 1에서 시작하고, 이후의 각 선분은 바로 앞 선분이 끝난 곳에서 시작하며, 마지막 선분은 점 16에서 끝난다. 선분의 길이와 방향은 자유이고, 꺾이는 지점이 점 위일 필요는 없으며 격자 바깥이어도 된다. 선분끼리 교차하거나 겹쳐도 된다.

선분 위에 있는 점은 연필이 그 위를 지나는 순간 방문한 것으로 본다. 그래서 목표한 점으로 가는 도중에 다른 점을 지나쳐도 된다. 예를 들어 처음 네 점을 1, 4, 2, 3, 2, 4, ... 순서로 방문해도 된다. 정확히 말하면, 방문한 점의 번호를 순서대로 나열한 수열에 1, 2, ..., 16이 부분 수열로 나타나야 한다.

위 그림은 첫 번째 예제의 답 하나를 보여 준다.

시모네는 이 퍼즐이 너무 어려울 것이라며 풍선 하나를 걸었다. 퍼즐을 대신 풀어 주는 프로그램을 작성해서 시모네가 틀렸음을 보이자.

입력은 4개의 줄로 이루어지며, 각 줄에 정수 4개가 주어진다. i번째 줄의 j번째 정수는 격자의 i번째 행 j번째 열에 있는 점의 번호다.

16개의 번호는 모두 1 이상 16 이하이고 서로 다르다.

모든 점을 번호 순서대로 잇는 데 필요한 선분 개수의 최솟값을 출력한다.