#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;

//#define N 4
//#define N2 16
//#define MAXDEPTH 45
//set<string> st;
//ll ans = 0;
//vector<ll> vec[N2];
//
//struct Puzzle{
//    string str;
//    ll piv;
//    ll depth;
//};
//
//void vec_init(){
//  rep(i,N2){
//    if(i % N != 0){
//      vec[i].push_back(i-1);
//    }
//    if(i % N != N-1){
//      vec[i].push_back(i+1);
//    }
//    if(i / N != 0){
//      vec[i].push_back(i-N);
//    }
//    if(i / N != N-1){
//      vec[i].push_back(i+N);
//    }
//  }
//}
//ll bfs(string s,ll piv){
////  queue<pair<string,ll>> q;
////  pair<string,ll> pa1,pa2;
////  pa1 = make_pair(s,0);
////  q.push(pa1);
//  //cout << s << endl;
//  queue<Puzzle> q;
//  Puzzle p1;
//  p1.str = s;
//  p1.depth = 0;
//  p1.piv = piv;
//  q.push(p1);
//  while(!q.empty()){
//    Puzzle p1 = q.front();
//    q.pop();
//    //cout << p1.str << endl;
//    if(st.find(p1.str) != st.end() || p1.depth > 45){
//      continue;
//    }
//    st.insert(p1.str);
//    bool can = true;
//    rep(i,N2){
//      if(p1.str[i] != (char)(i + 'a' + 1)){
//        can = false;
//      }
//    }
//    if(can){
//      return p1.depth;
//    }
//    for(auto itr:vec[p1.piv]){
//      Puzzle p2 = p1;
//      p2.depth = p1.depth+1;
//      swap(p2.str[p2.piv],p2.str[itr]);
//      p2.piv = itr;
//      q.push(p2);
//    }
//  }
//  return -1;
//}
//
//
//int main(){
//  ll piv;
//  string str = "";
//  rep(i,N2){
//    cin >> t1;
//    if(t1 == 0){
//      t1 += 16;
//      piv = i;
//    }
//    str += (char)t1 + 'a';
//  }
//  vec_init();
//  cout << bfs(str,piv) << endl;
//}







#define N 4
#define N2 16
#define LIMIT 100

static const int dx[4] = {0,-1,0,1};
static const int dy[4] = {1,0,-1,0};
static const char dir[4] = {'r','u','l','d'};
vector<vector<ll>> MDT(N2,vector<ll>(N2));

struct Puzzle {
    vector<ll> f;
    ll space;
    ll MD;
};

Puzzle state;
ll limit;//深さの制限
vector<ll> path(LIMIT);

ll getAllMD(Puzzle pz){
  ll sum = 0;
  rep(i,N2){
    if(pz.f[i] == N2){
      continue;
    }
    sum += MDT[i][pz.f[i] - 1];
  }
  return sum;
}

bool isSolved(){
  rep(i,N2){
    if(state.f[i] != i+1)return false;
  }
  return true;
}

bool dfs(ll depth,ll prev){
  if(state.MD == 0){return true;}

  //現在の深さにヒューリスティックを足して制限を超えたら枝を刈る
  if(depth + state.MD > limit){
    return false;
  }

  ll sx = state.space / N;
  ll sy = state.space % N;
  Puzzle tmp;

  rep(r,4){
    ll tx = sx + dx[r];
    ll ty = sy + dy[r];
    if(tx < 0 || ty < 0 || tx >= N || ty >= N)continue;
    if(max(prev,(ll)r) - min(prev,(ll)r) == 2)continue;
    tmp = state;
//    rep(i,N2){
//      cout << tmp.f[i] << " ";
//    }
//    cout << endl;

    //マンハッタン距離の差分を計算しつつ、ピースをスワップ
    state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1];
    state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1];
    swap(state.f[tx * N + ty],state.f[sx * N + sy]);
    state.space = tx * N + ty;
    if(dfs(depth+1,r)){
      path[depth] = r;
      return true;
    }
    state = tmp;
  }
  return false;
}

/*反復深化*/
string iterative_deepening(Puzzle in){
  in.MD = getAllMD(in); //初期状態のマンハッタン距離
  for(limit = in.MD;limit <= LIMIT;limit++){
    //cout << limit << endl;
    state = in; //deep copy
    if(dfs(0,-100)){
      string ans = "";
      rep(i,limit){
        ans += dir[path[i]];
      }
      return ans;
    }
  }
  return "unsolvable";
}

int main(){
  rep(i,N2){
    rep(j,N2){
      MDT[i][j] = abs(i / N - j / N) + abs(i % N - j % N);
    }
  }
  Puzzle in;
  in.f.resize(N2);
  in.MD = 0;

  rep(i,N2){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] = N2;
      in.space = i;
    }
  }
  string ans = iterative_deepening(in);
  cout << ans.size() << endl;

  return 0;
}



Measured memory_bytes: 3216