#include<stdio.h>
#define N 4
#define N2 16
#define MAX 101000000//スタックのサイズ
 
typedef struct{
  int m[N][N];
  int space;//左上0として空白のいちを示す(0=8)
  int man;
  int before;//前に数字の方向に進んだ
  int changetime;
}MAS;
MAS S[MAX];//これがスタックの本体
MAS Input={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0};

MAS ans={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,0,0};
int top=0;//スタックのてっぺん
int manlimit;
int way[4];//次に進む方向　上右下左
int plus=0;
//==================================
void Swap(int *a,int *b){ 
  int c=*a;
  *a=*b;
  *b=c;
}
//Que==================================Stack
int isFull(){//満タンだったら1 違ったら0
  if(top>=MAX-1){
    printf("full error\n");
    return 1;
  }
  return 0;
}
int isEmpty(){//空だったら1 　違ったら0
  if(top==0){
    return 1;
  }
  return 0;
}
void Push(MAS x){
  if(isFull()==1)return ;//error
  S[++top]=x;
}
MAS Pop(void){
  top--;
  return S[top+1];
}
//========================================
int Judge(MAS A,MAS B){//成功していたら1 失敗していたら0//２つの並びが同じか確かめる
  int i,j;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(A.m[i][j]!=B.m[i][j])return 0;
    }
  }
  return 1;
}
int Zetaiti(int a){
  return a<0?-a:a;}

int Mancalfirst(MAS child){//マンハッタン距離を返す
  int result=0;
  int i,j,k,l;
  int count;
  int x,y;
 
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(child.m[i][j]!=ans.m[i][j]&&child.m[i][j]!=0){
	for(k=0;k<N;k++){
	  for(l=0;l<N;l++){
	    if(child.m[i][j]==ans.m[k][l]){
	      result+=Zetaiti(i-k)+Zetaiti(j-l);
	      break;
	    }
	  }
	}
      }
    }
  }
  return result;
}

void Mancal(MAS *child,int i,int j,int x,int y){//マンハッタン距離の更新
  //[i][j]にある数が、空白ある場所と入れ替わった。
  //空白はmanにふくめないので　、空白は考えない
  //[i][j]
  int k,l;
  int a;
  int before;
  int after;
  int flag=0;
  a=child->m[i][j];
  for(k=0;k<N;k++){
    for(l=0;l<N;l++){
      if(a==ans.m[k][l]){//空白だった　今は新しい値がいる
	after=Zetaiti(i-k)+Zetaiti(j-l);//空白のマンハッタン
	before=Zetaiti(x-k)+Zetaiti(y-l);//移動後の　マンハッタン
	flag=1;
	break;
      }
    }
    if(flag)break;
  }
  if(after-before<0)child->man--;//近くなった
  else child->man++;
}

void  Way(MAS u){//次に進める方向を教える　進めない方向は0　すすめるのは1
  int i;
  for(i=0;i<4;i++)way[i]=1;//初期化;
  if(u.space<=3||u.before==2)way[0]--;//上
  if(u.space==3||u.space==7||u.space==11||u.space==15||u.before==3)way[1]--;//右
  if(u.space>=12||u.before==0)way[2]--;//下
  if(u.space%4==0||u.before==1)way[3]--;//左
}
//=======================================================================================
int  DFS(int limitchangetime){//何回で解けたか返す
  
  MAS u;
  MAS child;
  int count=0;
  int i;
  int flag=0;
 
  Push(Input);
  if(Input.man==0)return Input.changetime;
  
  while(!isEmpty()){
    u=Pop();
    Way(u);
    child=u;

    if(way[0]==1){
      Swap(&child.m[child.space/N][child.space%N],&child.m[child.space/N-1][child.space%N]);
      child.changetime++;
      child.before=0;
      Mancal(&child,child.space/N,child.space%N,child.space/N-1,child.space%N);

      if(child.man==0)return child.changetime;
      child.space-=N;
      if(limitchangetime>=child.changetime+child.man )Push(child);
    }   
      
    child=u;	
    if(way[1]==1){
      Swap(&child.m[child.space/N][child.space%N],&child.m[child.space/N][child.space%N+1]); 
      child.changetime++;
      child.before=1;

      Mancal(&child,child.space/N,child.space%N,child.space/N,child.space%N+1);
      if(child.man==0)return child.changetime;
      child.space++;
      if(limitchangetime>=child.changetime+child.man )Push(child);
    }
    
    child=u;	
    if(way[2]==1){
      Swap(&child.m[child.space/N][child.space%N],&child.m[child.space/N+1][child.space%N]); 
      child.changetime++;
      child.before=2;
      
      Mancal(&child,child.space/N,child.space%N,child.space/N+1,child.space%N);
      if(child.man==0)return child.changetime;
      child.space+=N;
      if(limitchangetime>=child.changetime+child.man )Push(child);
    }
    
    child=u;	
    if(way[3]==1){
      Swap(&child.m[child.space/N][child.space%N],&child.m[child.space/N][child.space%N-1]);
      child.changetime++;
      child.before=3;

      Mancal(&child,child.space/N,child.space%N,child.space/N,child.space%N-1);
      if(child.man==0)return child.changetime;
      child.space--;
      if(limitchangetime>=child.changetime+child.man )Push(child);
    }
  }
  return DFS(limitchangetime+1);
}

int main(){
  int i,j;
  int limit;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      scanf("%d",&Input.m[i][j]);
      if(Input.m[i][j]==0)Input.space=i*N+j;
    }
  }
  Input.man = Mancalfirst(Input);
  limit= Mancalfirst(Input);//0に代入してみる
  printf("%d\n",DFS(limit));
  return 0;
}



Measured memory_bytes: 2148