#include <bits/stdc++.h>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
typedef pair<int, int> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<int> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

bool up(vector<int> &board) {
    auto it = find(board.begin(), board.end(), 0);
    int id = distance(board.begin(), it);
    if (id == 0 || id == 1 || id == 2 || id == 3) {
        return false;
    }
    swap(board[id], board[id - 4]);
    return true;
}

bool down(vector<int> &board) {
    auto it = find(board.begin(), board.end(), 0);
    int id = distance(board.begin(), it);
    if (id == 12 || id == 13 || id == 14 || id == 15) {
        return false;
    }
    swap(board[id], board[id + 4]);
    return true;
}

bool right(vector<int> &board) {
    auto it = find(board.begin(), board.end(), 0);
    int id = distance(board.begin(), it);
    if (id == 3 || id == 7 || id == 11 || id == 15) {
        return false;
    }
    swap(board[id], board[id + 1]);
    return true;
}

bool left(vector<int> &board) {
    auto it = find(board.begin(), board.end(), 0);
    int id = distance(board.begin(), it);
    if (id == 0 || id == 4 || id == 8 || id == 12) {
        return false;
    }
    swap(board[id], board[id - 1]);
    return true;
}

const vector<int> clear = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};

bool is_enable(int depth, vector<int> &board, int ma) {

    int ans = 0;
    rep(i, 16) {
        if (i == 0) continue;
        auto b_it = find(board.begin(), board.end(), i);
        int b_id = distance(board.begin(), b_it);

        int b_x = b_id % 4;
        int b_y = b_id / 4;

        auto c_it = find(clear.begin(), clear.end(), i);
        int c_id = distance(clear.begin(), c_it);

        int c_x = c_id % 4;
        int c_y = c_id / 4;
        int now = abs(b_x - c_x) + abs(b_y - c_y);
        ans += now;
    }

    if (ans + depth <= ma) {
        return true;
    } else {
        return false;
    }

}


int dfs(vector<int> &board, char c, int depth, int ma) {

    if (board == clear) {
        return depth;
    }


    int ans = INF;
    if (c != 'd' && up(board)) {
        if (is_enable(depth + 1, board, ma)) {
            int now = dfs(board, 'u', depth + 1, ma);
            cmin(ans, now);

        }
        down(board);
    }
    if (c != 'u' && down(board)) {
        if (is_enable(depth + 1, board, ma)) {
            int now = dfs(board, 'd', depth + 1, ma);
            cmin(ans, now);

        }
        up(board);
    }
    if (c != 'r' && left(board)) {
        if (is_enable(depth + 1, board, ma)) {
            int now = dfs(board, 'l', depth + 1, ma);
            cmin(ans, now);

        }
        right(board);
    }
    if (c != 'l' && right(board)) {
        if (is_enable(depth + 1, board, ma)) {
            int now = dfs(board, 'r', depth + 1, ma);
            cmin(ans, now);

        }
        left(board);
    }
    return ans;

}

int main() {
    vector<int> board(16, 0);
    rep(i, 16) cin >> board[i];
    for (int i = 1; i <= 45; i++) {
        int ans = dfs(board, ' ', 0, i);
        if (ans != INF) {
            cout << ans << endl;
            return 0;
        }
    }

}


Measured memory_bytes: 3124