//config = { input: 'tmp', newline: '\r\n' }; // win
config = { input: '/dev/stdin', newline: '\n' }; // linux

board = require('fs').readFileSync(config.input, 'ascii')
  .trim()
  .split(config.newline)
  .map(function (line) { return line.split(' ').map(Number); })

const MAXSIZE = 45;
const SIZE = 4;

stack = new Array(MAXSIZE);
for (i = 0; i < MAXSIZE; i++) stack[i] = -1;

function iddfs(board, max, stack) {
  var step, i, j, cur;
  var r; // temporary row variable
  var row, col;
  step = 0;
  stack[0] = 0;
  for (i = 0; i < SIZE; i++) {
    for (j = 0; j < SIZE; j++) {
      if (board[i][j] === 0) {
        row = i;
        col = j;
      }
    }
  }
  while (step >= 0) {
    //console.log("step=%d, stack[step]=%d", step, stack[step]);
    if (step === max) {
      if ( (r = board[0])[0] === 1 && r[1] === 2 && r[2] === 3 && r[3] === 4
        && (r = board[1])[0] === 5 && r[1] === 6 && r[2] === 7 && r[3] === 8
        && (r = board[2])[0] === 9 && r[1] ===10 && r[2] ===11 && r[3] ===12
        && (r = board[3])[0] ===13 && r[1] ===14 && r[2] ===15 && r[3] === 0 )
      {
        return true;
      }
      --step;
      continue;
    }
    cur = stack[step];
    if (cur === 8) {
      --step;
      continue;
    }
    if (cur < 4) {
      if (cur < 2) {
        if (cur < 1) {
          /* cur === 0 */
          if (col > 0) {
            board[row][col] = board[row][col-1];
            board[row][--col] = 0;
            stack[step] = 4;
            stack[++step] = 0;
          } else {
            stack[step] = 1;
          }
        } else {
          /* cur === 1 */
          if (col < 3) {
            board[row][col] = board[row][col+1];
            board[row][++col] = 0;
            stack[step] = 5;
            stack[++step] = 0;
          } else {
            stack[step] = 2;
          }
        }
      } else {
        if (cur < 3) {
          /* cur === 2 */
          if (row > 0) {
            board[row][col] = board[row-1][col];
            board[--row][col] = 0;
            stack[step] = 6;
            stack[++step] = 0;
          } else {
            stack[step] = 3;
          }
        } else {
          /* cur === 3 */
          if (row < 3) {
            board[row][col] = board[row+1][col];
            board[++row][col] = 0;
            stack[step] = 7;
            stack[++step] = 0;
          } else {
            stack[step] = 8;
          }
        }
      }
    } else {
      if (cur < 6) {
        if (cur < 5) {
          /* cur === 4 */
          board[row][col] = board[row][col+1];
          board[row][++col] = 0;
          stack[step] = 1;
        } else {
          /* cur === 5 */
          board[row][col] = board[row][col-1];
          board[row][--col] = 0;
          stack[step] = 2;
        }
      } else {
        if (cur < 7) {
          /* cur === 6 */
          board[row][col] = board[row+1][col];
          board[++row][col] = 0;
          stack[step] = 3;
        } else {
          /* cur === 7 */
          board[row][col] = board[row-1][col];
          board[--row][col] = 0;
          stack[step] = 8;
        }
      }
    }
  } // end of while loop
  return false;
} // end of function

for (i = 0; i <= 45; i++)
  if (iddfs(board, i, stack)) break;
console.log(i);