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

using namespace std;

int minimum = -1;


int calcDiffSum(int table[4][4]){
    int sum = 0;
    for(int row=0;row<4;row++){
        for(int col=0;col<4;col++){
            if(table[row][col] != 0){
                sum += abs((table[row][col]-1)/4-row) + abs((table[row][col]-1)%4-col);
            }
        }
    }
    return sum;
}

int zeroLoc(int table[4][4]){
    int zero_loc;
    for(int i=0;i<4;i++){
        for(int k=0;k<4;k++){
            if(table[i][k]==0){
                zero_loc=10*i+k;
            }
        }
    }
    return zero_loc;
}

void recursive(int table[4][4],int max_depth,int count,int pre_loc,int zero_loc){
	int diffSum = calcDiffSum(table);
	if(count == max_depth && diffSum == 0){
		minimum = max_depth;
		return;
	}

	if(minimum != -1)return;

	int next_table[4][4][4],tmp_row,tmp_col,pre_row,pre_col;
	int dif1,dif2,dif3,dif4;


	switch(zero_loc){
	case 0:
		for(int a=0;a<2;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(pre_loc != 1){
			if((table[0][1]-1)%4==0){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}
			swap(next_table[0][0][0],next_table[0][0][1]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,1);
			}
		}
		if(pre_loc != 10){
			if((table[1][0]-1)/4==0){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}
			swap(next_table[1][0][0],next_table[1][1][0]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,10);
			}
		}
		break;
	case 1:
	case 2:
		tmp_row = zero_loc/10,tmp_col = zero_loc%10;
		pre_row = pre_loc/10,pre_col = pre_loc%10;

		for(int a=0;a<3;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col+1){
			if((table[tmp_row][tmp_col-1]-1)%4>=tmp_col){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}
			swap(next_table[0][tmp_row][tmp_col],next_table[0][tmp_row][tmp_col-1]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,10*tmp_row+tmp_col-1);
			}
		}

		if(tmp_row!=pre_row-1||tmp_col!=pre_col){
			if((table[tmp_row+1][tmp_col]-1)/4<=tmp_row){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}
			swap(next_table[1][tmp_row][tmp_col],next_table[1][tmp_row+1][tmp_col]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,10*(tmp_row+1)+tmp_col);
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col-1){
			if((table[tmp_row][tmp_col+1]-1)%4<=tmp_col){
				dif3 = diffSum - 1;
			}else{
				dif3 = diffSum + 1;
			}

			swap(next_table[2][tmp_row][tmp_col],next_table[2][tmp_row][tmp_col+1]);
			if(count < max_depth && dif3 <= max_depth-count){
				recursive(next_table[2],max_depth,count+1,zero_loc,10*tmp_row+tmp_col+1);
			}
		}
		break;
	case 3:
		for(int a=0;a<2;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(pre_loc != 2){
			if((table[0][2]-1)%4==3){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}

			swap(next_table[0][0][3],next_table[0][0][2]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,2);
			}
		}
		if(pre_loc != 13){
			if((table[1][3]-1)/4==0){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}

			swap(next_table[1][0][3],next_table[1][1][3]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,13);
			}
		}
		break;
	case 10:
	case 20:
		tmp_row = zero_loc/10,tmp_col = zero_loc%10;
		pre_row = pre_loc/10,pre_col = pre_loc%10;

		for(int a=0;a<3;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(tmp_row!=pre_row+1||tmp_col!=pre_col){
			if((table[tmp_row-1][tmp_col]-1)/4>=tmp_row){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}
			swap(next_table[0][tmp_row][tmp_col],next_table[0][tmp_row-1][tmp_col]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,10*(tmp_row-1)+tmp_col);
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col-1){
			if((table[tmp_row][tmp_col+1]-1)%4<=tmp_col){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}
			swap(next_table[1][tmp_row][tmp_col],next_table[1][tmp_row][tmp_col+1]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,10*tmp_row+tmp_col+1);
			}
		}

		if(tmp_row!=pre_row-1||tmp_col!=pre_col){
			if((table[tmp_row+1][tmp_col]-1)/4<=tmp_row){
				dif3 = diffSum - 1;
			}else{
				dif3 = diffSum + 1;
			}

			swap(next_table[2][tmp_row][tmp_col],next_table[2][tmp_row+1][tmp_col]);
			if(count < max_depth && dif3 <= max_depth-count){
				recursive(next_table[2],max_depth,count+1,zero_loc,10*(tmp_row+1)+tmp_col);
			}
		}
		break;
	case 11:
	case 12:
	case 21:
	case 22:
		tmp_row = zero_loc/10,tmp_col = zero_loc%10;
		pre_row = pre_loc/10,pre_col = pre_loc%10;

		for(int a=0;a<4;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col+1){
			if((table[tmp_row][tmp_col-1]-1)%4>=tmp_col){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}
			swap(next_table[0][tmp_row][tmp_col],next_table[0][tmp_row][tmp_col-1]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,10*tmp_row+tmp_col-1);
			}
		}

		if(tmp_row!=pre_row+1||tmp_col!=pre_col){
			if((table[tmp_row-1][tmp_col]-1)/4>=tmp_row){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}
			swap(next_table[1][tmp_row][tmp_col],next_table[1][tmp_row-1][tmp_col]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,10*(tmp_row-1)+tmp_col);
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col-1){
			if((table[tmp_row][tmp_col+1]-1)%4<=tmp_col){
				dif3 = diffSum - 1;
			}else{
				dif3 = diffSum + 1;
			}

			swap(next_table[2][tmp_row][tmp_col],next_table[2][tmp_row][tmp_col+1]);
			if(count < max_depth && dif3 <= max_depth-count){
				recursive(next_table[2],max_depth,count+1,zero_loc,10*tmp_row+tmp_col+1);
			}
		}

		if(tmp_row!=pre_row-1||tmp_col!=pre_col){
			if((table[tmp_row+1][tmp_col]-1)/4<=tmp_row){
				dif4 = diffSum - 1;
			}else{
				dif4 = diffSum + 1;
			}

			swap(next_table[3][tmp_row][tmp_col],next_table[3][tmp_row+1][tmp_col]);
			if(count < max_depth && dif4 <= max_depth-count){
				recursive(next_table[3],max_depth,count+1,zero_loc,10*(tmp_row+1)+tmp_col);
			}
		}
		break;
	case 13:
	case 23:
		tmp_row = zero_loc/10,tmp_col = zero_loc%10;
		pre_row = pre_loc/10,pre_col = pre_loc%10;

		for(int a=0;a<3;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(tmp_row!=pre_row+1||tmp_col!=pre_col){
			if((table[tmp_row-1][tmp_col]-1)/4>=tmp_row){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}

			swap(next_table[0][tmp_row][tmp_col],next_table[0][tmp_row-1][tmp_col]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,10*(tmp_row-1)+tmp_col);
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col+1){
			if((table[tmp_row][tmp_col-1]-1)%4>=tmp_col){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}

			swap(next_table[1][tmp_row][tmp_col],next_table[1][tmp_row][tmp_col-1]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,10*tmp_row+tmp_col-1);
			}
		}

		if(tmp_row!=pre_row-1||tmp_col!=pre_col){
			if((table[tmp_row+1][tmp_col]-1)/4<=tmp_row){
				dif3 = diffSum - 1;
			}else{
				dif3 = diffSum + 1;
			}

			swap(next_table[2][tmp_row][tmp_col],next_table[2][tmp_row+1][tmp_col]);
			if(count < max_depth && dif3 <= max_depth-count){
				recursive(next_table[2],max_depth,count+1,zero_loc,10*(tmp_row+1)+tmp_col);
			}
		}

		break;
	case 30:

		for(int a=0;a<2;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(pre_loc != 20){
			if((table[2][0]-1)/4==3){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}

			swap(next_table[0][3][0],next_table[0][2][0]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,20);
			}
		}

		if(pre_loc != 31){
			if((table[3][1]-1)%4==0){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;;
			}

			swap(next_table[1][3][0],next_table[1][3][1]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,31);
			}
		}
		break;
	case 31:
	case 32:
		tmp_row = zero_loc/10,tmp_col = zero_loc%10;
		pre_row = pre_loc/10,pre_col = pre_loc%10;

		for(int a=0;a<3;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col+1){
			if((table[tmp_row][tmp_col-1]-1)%4>=tmp_col){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}

			swap(next_table[0][tmp_row][tmp_col],next_table[0][tmp_row][tmp_col-1]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,10*tmp_row+tmp_col-1);
			}
		}

		if(tmp_row!=pre_row+1||tmp_col!=pre_col){
			if((table[tmp_row-1][tmp_col]-1)/4>=tmp_row){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}

			swap(next_table[1][tmp_row][tmp_col],next_table[1][tmp_row-1][tmp_col]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,10*(tmp_row-1)+tmp_col);
			}
		}

		if(tmp_row!=pre_row||tmp_col!=pre_col-1){
			if((table[tmp_row][tmp_col+1]-1)%4<=tmp_col){
				dif3 = diffSum - 1;
			}else{
				dif3 = diffSum + 1;
			}

			swap(next_table[2][tmp_row][tmp_col],next_table[2][tmp_row][tmp_col+1]);
			if(count < max_depth && dif3 <= max_depth-count){
				recursive(next_table[2],max_depth,count+1,zero_loc,10*tmp_row+tmp_col+1);
			}
		}
		break;
	case 33:

		for(int a=0;a<2;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					next_table[a][b][c] = table[b][c];
				}
			}
		}

		if(pre_loc != 23){
			if((table[2][3]-1)/4==3){
				dif1 = diffSum - 1;
			}else{
				dif1 = diffSum + 1;
			}

			swap(next_table[0][3][3],next_table[0][2][3]);
			if(count < max_depth && dif1 <= max_depth-count){
				recursive(next_table[0],max_depth,count+1,zero_loc,23);
			}
		}

		if(pre_loc != 32){
			if((table[3][2]-1)%4==3){
				dif2 = diffSum - 1;
			}else{
				dif2 = diffSum + 1;
			}

			swap(next_table[1][3][3],next_table[1][3][2]);
			if(count < max_depth && dif2 <= max_depth-count){
				recursive(next_table[1],max_depth,count+1,zero_loc,32);
			}
		}
		break;
	}
}


void func(int table[4][4],int max_depth){
	while(minimum == -1 && max_depth<=45){
		recursive(table,max_depth,0,-1,zeroLoc(table));
		max_depth += 2;
	}
}


int main(){

    int table[4][4],start_count;

    for(int i=0;i<4;i++){
        scanf("%d %d %d %d",&table[i][0],&table[i][1],&table[i][2],&table[i][3]);
    }
    start_count = calcDiffSum(table);

    func(table,start_count);

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

    return 0;
}

Measured memory_bytes: 2768