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

#define size 4
#define size2 16
#define size3 10000000
#define max 46

typedef struct {
  int b[size][size],m,cost, space[2], dis;
} Pz;

//int head=0, tail=0;
int h=0;
Pz q[size3];

/*
void enq(Pz pz){
  q[tail]=pz;
  tail = (tail+1)%size3;
}

Pz deq(void){
  int t;
  
  t = head;
  head = (head+1)%size3;

  return q[t];
}
*/

void mh(int i){
  int l,r,small;
  Pz t;

  while(1){
    l=i*2;
    r=i*2+1;

    if(l<=h && q[l].cost + q[l].dis < q[i].cost + q[i].dis)small = l;
    else small = i;
    if(r<=h && q[r].cost + q[r].dis < q[small].cost + q[small].dis)small = r;

    if(small!=i){
      t=q[small];
      q[small]=q[i];
      q[i]=t;

      i=small;
    }
    else break;
  }
}

void enq(Pz pz){
  Pz t;
  int tt;

  //printf("enq\n");
  h++;
  q[h] = pz;
  tt=h;

  while(1<tt && q[tt/2].cost + q[tt/2].dis > q[tt].cost + q[tt].dis){
    t=q[tt];
    q[tt]=q[tt/2];
    q[tt/2]=t;
    tt=tt/2;
  }
}

Pz deq(void){
  Pz t;

  t = q[1];
  q[1] = q[h];
  h--;
  mh(1);

  return t;
}

int check(Pz pz){
  int i,j;

  pz.b[pz.space[0]][pz.space[1]] = size2;
  
  for(i=0;i<size;i++){
    for(j=0;j<size;j++){
      if(pz.b[i][j] != i*size + j + 1){
	return 0;
      }
    }
  }

  return 1;
}

int distance(Pz pz){
  int i,j,sum=0,t   ;
  /*
  for(i=0;i<size;i++){
    for(j=0;j<size;j++){
      printf("%2d ",pz.b[i][j]);
    }
    printf("\n");
  }
  //*/
  pz.b[pz.space[0]][pz.space[1]] = size2;
  for(i=0;i<size;i++){
    for(j=0;j<size;j++){
      t=pz.b[i][j]-1;
      if(t!=size2-1){
	sum += abs(i - t/size) + abs(j - t%size);
      }
    }
  }

  //printf("cost %d sum %d\n",pz.cost,sum);
  return sum;
}
int main(){
  int i,j,tate,yoko,ans=0,count=0,tmpi;
  char tmpc;
  Pz inisial, tmpp, tmpp2;

  for(i=0;i<size;i++){
    for(j=0;j<size;j++){
      scanf("%d",&inisial.b[i][j]);
      if(inisial.b[i][j]==0){
	inisial.space[0] = i;
	inisial.space[1] = j;
	//printf("space %d %d\n",i,j);
      }
      //printf("space %d %d\n count%d\n",inisial.space[0],inisial.space[1],count);
      count++;
    }
  }
  //printf("\nspace %d %d\n\n",inisial.space[0],inisial.space[1]);
  inisial.cost = 0;
  inisial.m = '0';

  enq(inisial);
  
  if(check(inisial)!=1){
    while(h!=size3){
      //printf("h = %d\n",h);
      tmpp2 = tmpp = deq();
      tate = tmpp.space[0];
      yoko = tmpp.space[1];

      if(tate != 0 && tmpp.m != '1'){
	tmpc = tmpp2.b[tate-1][yoko];
	tmpp2.b[tate-1][yoko] = tmpp2.b[tate][yoko];
	tmpp2.b[tate][yoko] = tmpc;
	tmpp2.space[0] = tmpp2.space[0] - 1;
	tmpp2.cost++;
	tmpp2.dis = distance(tmpp2);
	if(tmpp2.dis == 0){
	  ans = tmpp2.cost;
	  break;
	}
	if(tmpp2.cost + tmpp2.dis < max){
	  tmpp2.m = '2';
	  enq(tmpp2);
	}
      }
      tmpp2=tmpp;

      if(tate < size-1 && tmpp.m != '2'){
	tmpc = tmpp2.b[tate+1][yoko];
	tmpp2.b[tate+1][yoko] = tmpp2.b[tate][yoko];
	tmpp2.b[tate][yoko] = tmpc;
	tmpp2.space[0] = tmpp2.space[0] + 1;
	tmpp2.cost++;
	tmpp2.dis = distance(tmpp2);
	if(tmpp2.dis == 0){
	  ans = tmpp2.cost;
	  break;
	}
	if(tmpp2.cost + tmpp2.dis < max){
	  tmpp2.m = '1';
	  enq(tmpp2);
	}
      }
      tmpp2=tmpp;

      if(yoko != 0 && tmpp.m != '3'){
	tmpc = tmpp2.b[tate][yoko-1];
	tmpp2.b[tate][yoko-1] = tmpp2.b[tate][yoko];
	tmpp2.b[tate][yoko] = tmpc;
	tmpp2.space[1] = tmpp2.space[1] - 1;
	tmpp2.cost++;
	tmpp2.dis = distance(tmpp2);
	if(tmpp2.dis == 0){
	  ans = tmpp2.cost;
	  break;
	}
	if(tmpp2.cost + tmpp2.dis < max){
	  tmpp2.m = '4';
	  enq(tmpp2);
	}
      }
      tmpp2=tmpp;

      if(yoko < size-1 && tmpp.m != '4'){
	tmpc = tmpp2.b[tate][yoko+1];
	tmpp2.b[tate][yoko+1] = tmpp2.b[tate][yoko];
	tmpp2.b[tate][yoko] = tmpc;
	tmpp2.space[1] = tmpp2.space[1] + 1;
	tmpp2.cost++;
	tmpp2.dis = distance(tmpp2);
	if(tmpp2.dis == 0){
	  ans = tmpp2.cost;
	  break;
	}
	if(tmpp2.cost + tmpp2.dis < max){
	  tmpp2.m = '3';
	  enq(tmpp2);
	}
      }
    }
  }

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

  return 0;
}



Measured memory_bytes: 103980