#include <iostream>
#include <cassert>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) std::cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<std::endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}

template<typename T>
class Deque{
public:
  T *val;
  int sz;
  int length;
  int head, tail;
  
  Deque(){sz = 0, length = 0, val = new T[0];}
  Deque(int size, T init = T()){
    length = 1;
    while(length < size) length *= 2;
    val = new T[length];
    sz = size;
    head = 0;
    tail = 0;
    for(int i=0;i<size;i++) val[tail++] = init;
  }
  
  Deque(const Deque &t){
    sz = t.size();
    length = 1;
    while(length < sz) length *= 2;
    val = new T[length];
    head = 0;
    tail = 0;
    for(int i=0;i<sz;i++) val[tail++] = t[i];
  }

  ~Deque(){
    delete [] val;
  }
  
  Deque<T> operator = (const Deque<T> &t){
    delete [] val;
    sz = t.size();
    length = 1;
    while(length < sz) length *= 2;
    val = new T[length];
    head = 0;
    tail = 0;
    for(int i=0;i<sz;i++) val[tail++] = t[i];
    return t;
  };
  
  T& operator [] (int i){
    assert(0 <= i && i < sz);
    return head+i<length? val[head+i]:val[head+i - length];
  }
  T& operator [] (int i)const{
   assert(0 <= i && i < sz);
    return head+i<length? val[head+i]:val[head+i - length];
  }
  
  bool operator == (const Deque<T> &a)const{
    if(size() != a.size()) return 0;
    for(int i=0;i<size();i++)
      if(!((*this)[i] == a[i])) return 0;
    return 1;
  }
  
  bool operator < (const Deque<T> &a)const{
    if(size() != a.size()) return size() < a.size();
    for(int i=0;i<size();i++)
      if(!((*this)[i] == a[i])) return (*this)[i] < a[i];
    return false;
  }
  
  T& front(){return val[head];}
  T& back(){return val[(head + sz - 1) % length];}
  
  int size()const{return sz;}
  int empty()const{return sz == 0;}
  
  void resize(int n, T v=T()){
    while(n < size()) pop_back();
    while(n > size()) push_back_fast(v);
  }


  void increaseMemory(){
    int length_ = length;
    length = length * 2;
    if(length == 0) length = 1;
    T *val2 = new T[length];
    for(int i=0;i<sz;i++) val2[i] = val[(head + i)%length_];
    head = 0;
    tail = sz;
    delete [] val;
    val = val2;
  };
  
  void push_back(T v){
    if(sz == length) increaseMemory();
    sz++;
    val[tail++] = v;
    if(tail == length) tail = 0;
  }

  void push_back_fast(T &v){
    if(sz == length) increaseMemory();
    sz++;
    val[tail++] = v;
    if(tail == length) tail = 0;
  }
    
  void push_front(int v){
    if(sz == length) increaseMemory();
    sz++;
    head--;
    if(head == -1) head = length - 1;
    val[head] = v;
  }

  void pop_back(){
    assert(sz > 0);
    sz--;
    tail--;
    if(tail == -1) tail = length - 1;
  }
  
  void pop_front(){
    assert(sz > 0);
    sz--;
    head++;
    if(head == length) head = 0;
  }

  friend std::ostream& operator << (std::ostream& os,const Deque<T> a){
    os<<"[";
    for(int i=0;i<a.size();i++){
      if(i) os<<" ";
      os<<a[i];
    }
    os<<"]";
    return os;
  }
};
template <typename T>
using vector = Deque<T>;

template <typename T>
using queue = Deque<T>;

template <typename T, typename D>
class Pair{
public:
  T first;
  D second;
  Pair(){first = T(),second = D();}
  Pair(const T &first, const D &second):first(first), second(second){}
  
  bool operator < (const Pair &t)const{
    return first != t.first? (first < t.first):(second < t.second);
  }
  bool operator > (const Pair &t)const{
    return first != t.first? (first > t.first):(second > t.second);
  }
  
  bool operator == (const Pair &t)const{return first == t.first && second == t.second;}
  bool operator != (const Pair &t)const{return !(first == t.first && second == t.second);}

  
  friend std::ostream& operator << (std::ostream& os,const Pair<T, D> a){
    os<<"("<<a.first<<", "<<a.second<<")";
    return os;
  }
};

template<class T, class D>
class HashTable{
public:
  using ull = unsigned int;
  ull tableSize;
  vector<vector<T> > tableKey;
  vector<vector<D> > tableVal;
  
  HashTable(ull tableSize = 500009){
    for(int i=2;i*i<=tableSize;i++)
      assert(tableSize % i != 0 && "tableSize have to be prime number");
    this->tableSize = tableSize;
    tableKey.resize(tableSize);
    tableVal.resize(tableSize);

  }

  void push(T key, D val, ull hash){
    hash %= tableSize;
    tableKey[hash].push_back_fast(key);
    tableVal[hash].push_back_fast(val);
  }

  bool count(T key, ull hash){
    hash %= tableSize;
    int count = 0;
    for(int i=0;i<tableKey[hash].size();i++)
      if(tableKey[hash][i] == key) count++;
    return count;
  }

  bool exist(T key, ull hash){
    hash %= tableSize;
    for(int i=0;i<tableKey[hash].size();i++) if(tableKey[hash][i] == key) return true;
    return false;
  }
  
  D& getVal(T key, ull hash){
    hash %= tableSize;
    if(tableKey[hash].size() == 1) return tableVal[hash][0];
    for(int i=0;i<tableKey[hash].size();i++)
      if(tableKey[hash][i] == key) return tableVal[hash][i];
    
    assert(!"key not exists");
  }
};

template<class T>
void swap(T &a, T &b){
  T tmp = a;
  a = b;
  b = tmp;
}

template<typename T>
class Priority_queue{
public:
  T *A;
  int H;
  int limitSize;
  int sz;
  T MIN;

  constexpr Priority_queue(){H = 0, sz = 0;}
  constexpr Priority_queue(int size, T mn){
    MIN = mn;
    A = new T[size];
    H = 0;
    limitSize = size;
    sz = 0;
  }

  int size(){return sz;}
  int empty(){return sz == 0;}

  void swap(T &a, T & b){
    T tmp = a;
    a = b;
    b = tmp;
  }
  
  void maxHeapify(int i){
    int l=i * 2;
    int r=i * 2 + 1;
    int largest;
    if(l <= H && A[i] < A[l]) largest = l;
    else largest = i;
    
    if(r <=H && A[largest] < A[r]) largest = r;
   
    if(largest != i) {
      swap(A[i], A[largest]);
      maxHeapify(largest);
    }
  }
 
  void heapIncreaseKey(int i, const T &key){
    A[i] = key;
    while(i > 1 && A[i/2] < A[i]){
      swap(A[i], A[i/2]);
      i /= 2;
    }
  }
 
  void push(const T &k){
    assert(sz < limitSize);
    sz++;
    H++;
    A[H] = MIN;
    heapIncreaseKey(H, k);  
  }
  
  T top(){return A[1];}
  
  T pop(){
    sz--;
    T res = A[1];
    A[1] = A[H];
    H--;
    maxHeapify(1);
    return res;
  }
};


using D = vector<vector<int> >;
const int N = 4;

unsigned long long toHash(D &mp, const unsigned long long B){
  using ull = unsigned long long;
  ull hash = 0;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) hash = hash * B + mp[i][j];
  return hash;
}

unsigned long long getHash(D &mp,unsigned long long hash, int i, int j,int ni, int nj,int flag = 0){
  using ull = unsigned long long;
  static int init = 1;
  const ull B[2] = {17, 1777771};
  static ull pow[2][20];
  if(init){
    init = 0;
    for(int i=0;i<2;i++){
      pow[i][0] = 1;
      for(int j=1;j<20;j++) pow[i][j] = pow[i][j-1] * B[i];
    }
  }

  int idx1 = i * N + j;
  int idx2 = ni * N + nj;
  ull p1 = pow[flag][N * N - 1 - idx1];
  ull p2 = pow[flag][N * N - 1 - idx2];
  return hash - (mp[ni][nj] * p1 + mp[i][j] * p2) + (mp[i][j] * p1 + mp[ni][nj] * p2);
}

int calcCost(D &pos, D &goal){
  static int idxX[N * N], idxY[N * N], flag = 0;
  if(flag == 0){
    flag = 1;
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++) idxX[goal[i][j]] = j, idxY[goal[i][j]] = i;
  }
  
  auto abs = [](int a){return a < -a? -a:a;};
  int res = 0;  
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++){
      if(pos[i][j] == 0) continue;
      res += abs(i - idxY[pos[i][j]]) + abs(j - idxX[pos[i][j]]);
    }
  
  return res;
}

int calcDiff(D &pos, D &goal, int i, int j, int ni, int nj){
  static int idxX[N * N], idxY[N*N], flag = 0;
  if(flag == 0){
    flag = 1;
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++) idxX[goal[i][j]] = j, idxY[goal[i][j]] = i;
  }

  int a =
    (pos[ni][nj] != 0 ) * (abs(i - idxY[ pos[ni][nj] ]) + abs(j - idxX[ pos[ni][nj] ])) +
    (pos[i][j] != 0 ) * (abs(ni - idxY[ pos[i][j] ]) + abs(nj - idxX[ pos[i][j] ]));

  
  int b =
    (pos[i][j] != 0 ) * (abs(i - idxY[ pos[i][j] ]) + abs(j - idxX[ pos[i][j] ])) + 
    (pos[ni][nj] != 0 ) * (abs(ni - idxY[ pos[ni][nj] ]) + abs(nj - idxX[ pos[ni][nj] ]));
  return -a + b;
}

int dijkstra(D start, D goal){
  
  using ull = unsigned long long;
  const ull B1 = 17;
  const ull B2 = 1777771;
  const ull hashGoal = toHash(goal, B2);
  using P = Pair<int, short>;
  using Pu = Pair<ull, unsigned long long>;
  using PP = Pair<P, Pu>;
  Priority_queue <PP> Q(330000, PP(P(-100000000,-100), Pu(0, 0)));
  
  Q.push(PP(P(-calcCost(start, goal), 0), Pu(toHash(start, B2), toHash(start, B1))));
  
  HashTable <ull, int> memo(200017); //<key, val>
  HashTable <ull, D> memo2(200017); // <key, val>
  memo.push(toHash(start, B2), 0, toHash(start, B1));
  memo2.push(toHash(start, B2), start, toHash(start, B1));
  
  int cnt = 0;
  while(!Q.empty()){
    cnt++;
    int cost1 = -Q.top().first.first;
    int cost2 = Q.top().first.second;
    ull hash1 = Q.top().second.second;
    ull hash2 = Q.top().second.first;
    Q.pop();
    D mp = memo2.getVal(hash2, hash1);
    if(hash2 == hashGoal && mp == goal) return cost2;
    
    //if(cnt % 10000 == 0) pr(cnt, cost1, cost2, Q.size());
    
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++){
	if(j+1<N && (mp[i][j] == 0 || mp[i][j+1] == 0)){
	  D &key = mp; swap(key[i][j], key[i][j+1]);
	  int val = cost2 + 1;
	  ull nhash1 = getHash(key, hash1, i, j, i, j+1, 0);
	  ull nhash2 = getHash(key, hash2, i, j, i, j+1, 1);
	  if(!memo.exist(nhash2, nhash1)) {
	    memo.push(nhash2, val, nhash1);
	    memo2.push(nhash2, key, nhash1);
	    int ncost1 = cost1 + calcDiff(key, goal, i, j, i, j+1) + 1;
	    if(ncost1 <= 45) Q.push(PP(P(-ncost1, val), Pu(nhash2, nhash1)));
	    //assert(ncost1 == calcCost(key, goal) + val);
	    //assert(getHash(key, hash1, i, j, i, j+1, 0) == toHash(key, B1));
	    //assert(getHash(key, hash2, i, j, i, j+1, 1) == toHash(key, B2));
	      
	  }
	  swap(key[i][j], key[i][j+1]);
	}

	if(i+1<N && (mp[i][j] == 0 || mp[i+1][j] == 0)){
	  D &key = mp; swap(key[i][j], key[i+1][j]);
	  int val = cost2 + 1;
	  ull nhash1 = getHash(key, hash1, i, j, i+1, j, 0);
	  ull nhash2 = getHash(key, hash2, i, j, i+1, j, 1);
	  if(!memo.exist(nhash2, nhash1)) {
	    memo.push(nhash2, val, nhash1);
	    memo2.push(nhash2, key, nhash1);
	    int ncost1 = cost1 + calcDiff(key, goal, i, j, i + 1, j) + 1;
	    //assert(ncost1 == calcCost(key, goal) + val);
	    //assert(getHash(key, hash1, i, j, i+1, j, 0) == toHash(key, B1));
	    //assert(getHash(key, hash2, i, j, i+1, j, 1) == toHash(key, B2));
	    if(ncost1 <= 45) Q.push(PP(P(-ncost1, val), Pu(nhash2, nhash1)));
	  }
	  swap(key[i][j], key[i+1][j]);
	}
      }
  }
  assert(0);
}

signed main(){

  D goal(N, vector<int>(N));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) goal[i][j] = i*N + j + 1;
  goal[N-1][N-1] = 0;

  D start(N, vector<int>(N));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) std::cin>>start[i][j];

  
  int ans = dijkstra(start, goal);

  std::cout<<ans<<std::endl;
}



Measured memory_bytes: 222672