#include <stdio.h>
#include <math.h>

#define N 4

int search(int board[N][N], int min, int lim, int r_0, int c_0, char mv);

int main(int argc, char *argv[])
{
  int board[N][N];
  int md;
  int a, b, r, c, r_0, c_0, found;
  int res;

  for (a = 0; a < N; a++) {
    for (b = 0; b < N; b++) scanf("%d", &board[a][b]);
  }

  md = 0;
  for (a = 0; a < N * N; a++) {
    found = 0;
    for (r = 0; r < N; r++) {
      for (c = 0; c < N; c++) {
	if (board[r][c] == a) {
	  if (a == 0) {
	    r_0 = r;
	    c_0 = c;
	  } else md += (int)fabs((a-1)/N - r) + (int)fabs((a-1)%N - c);
	  found = 1;
	  break;
	}
      }
      if (found == 1) break;
    }
  }

  for (a = 0; ; a += 2) {
    if ((r_0 + c_0) % 2 == 0) {
      if (md % 2 == 0) res = search(board, md, md+a, r_0, c_0, 'c');
      else res = search(board, md, md+a+1, r_0, c_0, 'c');
    } else {
      if (md % 2 == 0) res = search(board, md, md+a+1, r_0, c_0, 'c');
      else res = search(board, md, md+a, r_0, c_0, 'c');
    }

    if (res != -1) break;
  }

  printf("%d\n", res);

  return 0;
}

int search(int board[N][N], int min, int lim, int r_0, int c_0, char mv)
{
  int md_c[4];
  int op[4], num[4];
  int res[4];
  int a;
  char dir[5] = "nswe";

  if (min == 0) return 0;

  for (a = 0; a < 4; a++) {
    md_c[a] = min;
    res[a] = -1;
  }
  op[0] = r_0-1;
  op[1] = r_0+1;
  op[2] = c_0-1;
  op[3] = c_0+1;

  if (op[0] >= 0) {
    if (mv != 's') {
      num[0] = board[op[0]][c_0];
      md_c[0] -= (int)fabs((num[0]-1)/N - op[0]);
      md_c[0] += (int)fabs((num[0]-1)/N - r_0);
    }
  }
  if (op[1] <= N-1) {
    if (mv != 'n') {
      num[1] = board[op[1]][c_0];
      md_c[1] -= (int)fabs((num[1]-1)/N - op[1]);
      md_c[1] += (int)fabs((num[1]-1)/N - r_0);
    }
  }
  if (op[2] >= 0) {
    if (mv != 'e') {
      num[2] = board[r_0][op[2]];
      md_c[2] -= (int)fabs((num[2]-1)%N - op[2]);
      md_c[2] += (int)fabs((num[2]-1)%N - c_0);
    }
  }
  if (op[3] <= N-1) {
    if (mv != 'w') {
      num[3] = board[r_0][op[3]];
      md_c[3] -= (int)fabs((num[3]-1)%N - op[3]);
      md_c[3] += (int)fabs((num[3]-1)%N - c_0);
    }
  }

  for (a = 0; a < 4; a++) {
    if (md_c[a] - min == -1) {
      if (a / 2 == 0) {
	board[op[a]][c_0] = 0;
	board[r_0][c_0] = num[a];
	res[a] = search(board, md_c[a], lim-1, op[a], c_0, dir[a]);
	if (res[a] == -1) {
	  board[op[a]][c_0] = num[a];
          board[r_0][c_0] = 0;
	} else res[a]++;
      } else {
	board[r_0][op[a]] = 0;
	board[r_0][c_0] = num[a];
	res[a] = search(board, md_c[a], lim-1, r_0, op[a], dir[a]);
	if (res[a] == -1) {
          board[r_0][op[a]] = num[a];
          board[r_0][c_0] = 0;
        } else res[a]++;
      }
    }

    if (res[a] != -1) break;
  }

  for (a = 0; a < 4; a++) {
    if (md_c[a] - min == 1) {
      if (md_c[a] <= lim - 1) {
	if (a / 2 == 0) {
	  board[op[a]][c_0] = 0;
	  board[r_0][c_0] = num[a];
	  res[a] = search(board, md_c[a], lim-1, op[a], c_0, dir[a]);
	  if (res[a] == -1) {
	    board[op[a]][c_0] = num[a];
	    board[r_0][c_0] = 0;
	  } else res[a]++;
	} else {
	  board[r_0][op[a]] = 0;
	  board[r_0][c_0] = num[a];
	  res[a] = search(board, md_c[a], lim-1, r_0, op[a], dir[a]);
	  if (res[a] == -1) {
	    board[r_0][op[a]] = num[a];
	    board[r_0][c_0] = 0;
	  } else res[a]++;
	}
      } else res[a] = -1;
    }
  }

  if (res[0] == -1 && res[1] == -1 && res[2] == -1 && res[3] == -1) return -1;
  else if (res[0] != -1) return res[0];
  else if (res[1] != -1) return res[1];
  else if (res[2] != -1) return res[2];
  else return res[3];
}



Measured memory_bytes: 2096