#ifdef LOCAL
#pragma GCC optimize ("O0")
#else
#pragma GCC optimize ("O3")
#endif


#include <bits/stdc++.h>


using namespace std;

using ll = long long;
const int INF = 1e9 + 7;
const int MOD = INF;
const ll INF_LL = 1e18 + 7;

#define __overload3(_1, _2, _3, name,...) name
#define rep(...) __overload3(__VA_ARGS__, repFromUntil, repUntil, repeat)(__VA_ARGS__)
#define repeat(times) repFromUntil(__name, 0, times)
#define repUntil(name, times) repFromUntil(name, 0, times)
#define repFromUntil(name, from, until) for (int name = from, name##__until = (until); name < name##__until; name++)
#define repFromTo(name, from, to) repFromUntil(name, from, to + 1)
#define repr(...) __overload3(__VA_ARGS__, reprFromUntil, reprUntil, repeat)(__VA_ARGS__)
#define reprUntil(name, times) reprFromUntil(name, 0, times)
#define reprFromUntil(name, from, until) for (int name = until - 1, name##__from = (from); name >= name##__from; name--)
#define reprFromTo(name, from, to) reprFromUntil(name, from, to + 1)

#define debugos OUT
#ifdef LOCAL
#define debug(v) {printf("L%d %s > ",__LINE__,#v);debugos<<(v)<<newl;}
#define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:(v)){debugos<<e<<" ";}debugos<<newl;}
#define debuga(m,w) {printf("L%d %s > ",__LINE__,#m);for(int x=0;x<(w);x++){debugos<<(m)[x]<<" ";}debugos<<newl;}
#define debugaa(m,h,w) {printf("L%d %s >\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){debugos<<(m)[y][x]<<" ";}debugos<<newl;}}
#else
#define debug(v) {}
#define debugv(v) {}
#define debuga(m,w) {}
#define debugaa(m,h,w) {}
#endif

#define newl "\n"

#define all(iter) begin(iter), end(iter)


template <class T> bool chmin(T& var, T x) {
  if (var > x) {
    var = x;
    return true;
  } else return false;
}
template <class T> bool chmax(T& var, T x) {
  if (var < x) {
    var = x;
    return true;
  } else return false;
}

class MyScanner {
  public:
    template<typename T> void input_integer(T& var) {
        var = 0; T sign = 1;
        int cc = getchar();
        for (; cc<'0' || '9'<cc; cc = getchar())
            if (cc == '-') sign = -1;
        for (; '0' <= cc && cc <= '9'; cc = getchar())
            var = (var << 3) + (var << 1) + cc - '0';
        var = var * sign;
    }
    int c() { char c; while (c = getchar(), c == ' ' or c == '\n'); return c; }
    MyScanner& operator>>(char& var) { var = c(); return *this; }
    MyScanner& operator>>(int& var) { input_integer<int>(var); return *this; }
    MyScanner& operator>>(ll& var) { input_integer<ll>(var); return *this; }
    MyScanner& operator>>(string& var) {
        int cc = getchar();
        for (; !isvisiblechar(cc); cc = getchar());
        for (; isvisiblechar(cc); cc = getchar())
            var.push_back(cc);
        return *this;
    }
    operator int() {
      int n;
      *this >> n;
      return n;
    }
    operator ll() {
      ll n;
      *this >> n;
      return n;
    }
    private:
      int isvisiblechar(int c) {
        return 0x21 <= c && c <= 0x7E;
      }
};
class MyPrinter {
  public:
    template<typename T>
    void output_integer(T var) {
        if (var == 0) { putchar('0'); return; }
        if (var < 0)
            putchar('-'),
            var = -var;
        char stack[32]; int stack_p = 0;
        while (var)
            stack[stack_p++] = '0' + (var % 10),
            var /= 10;
        while (stack_p)
            putchar(stack[--stack_p]);
    }
    MyPrinter& operator<<(char c) { putchar(c); return *this; }
    template <typename T>
    MyPrinter& operator<<(T var) { output_integer<T>(var); return *this; }
    MyPrinter& operator<<(char* str_p) { while (*str_p) putchar(*(str_p++)); return *this; }
    MyPrinter& operator<<(const char* str_p) { while (*str_p) putchar(*(str_p++)); return *this; }
    MyPrinter& operator<<(const string& str) {
        const char* p = str.c_str();
        const char* l = p + str.size();
        while (p < l) putchar(*p++);
        return *this;
    }
    // MyPrinter& operator<<(const modint& var) { output_integer<ll>(var.value); return *this; }
    template <typename T>
    void operator()(T x) {
        *this << x << newl;
    }
};
MyScanner IN;
MyPrinter OUT;

using T = vector<int>;

struct Node {
  T board;
  int cost;

  int at(int r, int c) {
    return board[r*4 + c];
  }

  Node(T board_, int cost_): board(board_), cost(cost_) {}

  int eval() {
    int score = 0;
    rep(r, 4) rep(c, 4) {
      if (at(r, c) == 0) {
        continue;
      }
      int dr = abs(r - (at(r, c)-1)/4);
      int dc = abs(c - (at(r, c)-1)%4);
      score += dr + dc;
    }
    return score;
  }

  vector<Node> next() {
    vector<Node> res;
    int ds[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int zero_r, zero_c;
    rep(r, 4) rep(c, 4) if (at(r, c) == 0) zero_r = r, zero_c = c;

    for (auto& d : ds) {
      int r1 = zero_r + d[0], c1 = zero_c + d[1];
      if (0 <= r1 and r1 < 4 and 0 <= c1 and c1 < 4) {
        T board1 = board;
        swap(board1[zero_r*4 + zero_c], board1[r1*4 + c1]);
        res.emplace_back(move(board1), cost + 1);
      }
    }
    return move(res);
  }

  bool operator ==(const Node &rhs) const {
    return board == rhs.board;
  }

  bool operator <(const Node &rhs) const {
    return cost > rhs.cost;
  }
};

int main() {
  T start_board(16);
  rep(i, 16) IN >> start_board[i];

  Node start{move(start_board), 0};
  Node goal{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}, -1};

  if (start == goal) {
    OUT(0);
    return 0;
  }

  using P = pair<int, Node>;
  priority_queue<P, vector<P>, greater<P>> q;
  set<vector<int>> done;
  done.insert(start.board);
  int s_start = start.eval();
  q.emplace(s_start, move(start));

  while (!q.empty()) {
    P p = move(q.top()); q.pop();
    // printf("%d %d %d\n", p.first, p.second.eval(), p.second.cost);
    auto nexts = p.second.next();
    for (Node &next : nexts) {
      if (next == goal) {
        OUT(next.cost);
        return 0;
      }
      if (done.find(next.board) == done.end()) {
        done.insert(next.board);
        int s = next.eval() + next.cost;
        q.emplace(s, move(next));
      }
    }
  }
}


Measured memory_bytes: 111412