#include <iostream>
#include <queue>
#include <unordered_map>
#include <map>

enum class Direction {
    UP,
    LEFT,
    DOWN,
    RIGHT,
    NOT_YET,
};

const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};

const std::string lastState = "0123456789ABCDEX";

std::pair<int, int> getPos(int pos) {
    return {pos / 4, pos % 4};
}

std::string manipulate(std::string state, Direction dir) {
    const auto pos = state.find('X');

    const auto current = getPos(pos);

    const auto px = current.second + dx[static_cast<int>(dir)];
    const auto py = current.first+ dy[static_cast<int>(dir)];

    if (px < 0 || px > 3 || py < 0 || py > 3) {
        return "";
    }

    std::swap(state[(py * 4 + px)], state[pos]);

    return state;
}

int h0(const std::string&) {
    return 0;
}

int h1(const std::string& s) {
    int ret = 0;
    for(int i = 0; i < s.size(); ++i) {
        if(s[i] != lastState[i]) {
            ++ret;
        }
    }

    return ret;
}

int h2(const std::string& s) {
    int ret = 0;
    for(int i = 0; i < s.size(); ++i) {
        if(s[i] == 'X')
            continue;

        const auto a = getPos(i);
        const auto b = getPos(lastState.find(s[i]));

        ret += std::abs(a.first - b.first) + std::abs(a.second - b.second);
    }

    return ret;
}

struct State {
    int estimated;
    int cost;

    std::string map;
    State(int cost, std::string map):cost(cost), map(map){
#if defined(HEURISTIC) && HEURISTIC == 0
        estimated = cost + h0(map);
#elif defined(HEURISTIC) && HEURISTIC == 1
        estimated = cost + h1(map);
#else
        estimated = cost + h2(map);
#endif
    };

    bool operator < (const State& second) const {
        return this->estimated < second.estimated;
    }
    bool operator > (const State& second) const {
        return this->estimated > second.estimated;
    }

    explicit operator bool () const {
        return map == lastState;
    }

    State(const State&) = default;
    State(State&&) = default;
    State& operator = (const State&) = default;
    State& operator = (State&&) = default;
};

std::string input16() {
    auto s = lastState;

    for (int i = 0; i < 4; ++i) {
        for(int j = 0; j < 4; ++j) {
            int n;
            std::cin >> n;
            if(n == 0) {
                s[i * 4 + j] = 'X';
            }else {
                s[i * 4 + j] = lastState[n - 1];
            }
        }
    }

    return s;
}

int main() {
    const auto str = input16();

    std::unordered_map<std::string, bool> best;
    std::priority_queue<State, std::vector<State>, std::greater<State>> que;
    que.emplace(0, str);

    while(!que.empty()) {
        const auto state = que.top();
        que.pop();

        if(state) {
            std::cout << state.cost << std::endl;

            return 0;
        }
        best[state.map] = state.cost;

        for(int i = 0; i < 4; ++i) {
            const auto next = manipulate(state.map, static_cast<Direction>(i));

            if(next == "") {
                continue;
            }

            const auto& it = best.find(next);
            if(it != best.end()/* it->second < state.cost+1*/) {
                continue;
            }

            que.emplace(state.cost+1, next);
        }
        
    }
}


Measured memory_bytes: 173196