#include <iostream>
#include <istream>
#include <ostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <random>
#include <tuple>
#include <functional>

using namespace std;

// Too slow to solve 15 puzzle problem.
//  

inline int abs(int i) {return i > 0 ? i : -i;}

constexpr int DEPTH_LIMIT = 45;
constexpr int W = 4;
constexpr int H = 4;
constexpr int WH = W * H;
constexpr unsigned long long init_key = 1311768467463790320ull;
enum class Direction {Left, Right, Up, Down};

struct Position
{
    int row;
    int col;
    bool slide(Direction d);
};

inline int pos2idx(const Position & pos) {return pos.row * W + pos.col;}

using Board = vector<int>;

unsigned long long calc_key(Board & board);

int calc_MHD(Board & board);

Position find_blank(Board & board);

class Status
{
public:
    // ctor
    Status() = default;
    Status(Board & board_, Position & blank_): board{board_}, blank{blank_} {mhd = calc_MHD(board_); key = calc_key(board_);};
    Status(Board & board_): board{board_} {blank = find_blank(board_); mhd = calc_MHD(board_); key = calc_key(board_);};
    // copy, move ctor
    Status(const Status & status) = default;
    Status(Status && status) = default;
    // copy, move assignment
    Status& operator=(const Status & status) = default;
    Status& operator=(Status && status) = default;
    //detor
    ~Status() = default;
    
    friend istream & operator>>(istream & is, Status & st);
    
    bool operator==(const Status & rhs) const {return key == rhs.key;};
    bool operator<(const Status & rhs) const {return key < rhs.key;};
    bool operator>(const Status & rhs) const {return key > rhs.key;};
    
    bool slide(Direction d);
    
    int get_mhd() const {return mhd;};
    Board get_board() const {return board;};
    unsigned long long get_key() const {return key;};

private:
    Board board = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};
    Position blank = {3, 3};
    int mhd = 0;
    unsigned long long key = init_key;
    void _update();
    void _update_after_slide(const Position & prev_blank);
};

istream & operator>>(istream & is, Board & board);

int solve(Status status);


////////////////////////////////////////////////
// main function
////////////////////////////////////////////////
int main()
{
    Status status;
    cin >> status;
    cout << solve(status) << endl;
    return 0;
}


////////////////////////////////////////////////

int solve(Status status){
    priority_queue< pair<int, Status>, vector< pair<int, Status> >, greater< pair<int, Status> > > pq;
    map<unsigned long long, int> k2s;
    
    pq.emplace(0 + status.get_mhd(), status);
    if (status.get_mhd() == 0) return 0;
    k2s[status.get_key()] = 0;
    while (not pq.empty()){
//        cout << pq.size() << ' ' << k2s.size() << endl;
        int p;
        Status st;
        tie(p, st) = pq.top();
        pq.pop();
        int steps = p - st.get_mhd();
        auto key_ = st.get_key();
        if (k2s[key_] < steps) continue;
        for (auto d : {Direction::Left, Direction::Right, Direction::Up, Direction::Down}){
            Status new_st{st};
            if (new_st.slide(d)){
                int new_p = steps + 1 + new_st.get_mhd();
                if (new_p > DEPTH_LIMIT) continue;
                auto new_key = new_st.get_key();
                auto it = k2s.find(new_key);
                if (it == k2s.end() or it->second > steps + 1){
                    k2s[new_key] = steps + 1;
                    pq.emplace(new_p, new_st);
                    if (new_st.get_mhd() == 0) return new_p;
                }
            }
        }
    }
    return -1;
}

unsigned long long calc_key(Board & board){
    unsigned long long key = 0;
    for (auto val : board){
        key *= WH;
        key += val;
    }
    return key;
}

int calc_MHD(Board & board){
    // Calculates the sum of Manhattan distances
    // from current position to goal position 
    // for all panels except blank (=0) panel. 
    int mhdist = 0;
    int src = 0;
    for (auto dst : board){
        if (dst == 0){
            ++src;
            continue;
        }
        dst = (dst + WH - 1) % WH;
        int drow = abs(src / W - dst / W);
        int dcol = abs(src % W - dst % W);
        mhdist += drow + dcol;
        ++src;
    }
    return mhdist;
}


Position find_blank(Board & board){
    // Find a blank (=0) panel on a board with width=W and height=H
    // and return its position (row, col).
    for(int i = 0; i != WH; ++i){
        if (board[i]) continue;
        return {i / W, i % W};
    }
}


istream & operator>>(istream & is, Board & board){
    for (int i = 0; i != WH; ++i){
        cin >> board[i];
    }
    return is;
}


istream & operator>>(istream & is, Status & st){
    is >> st.board;
    st._update();
    return is;
}

bool Position::slide(Direction d){
    switch(d){
        case Direction::Left:
            if (col <= 0) return false;
            --col;
            break;
        case Direction::Right:
            if (col >= W - 1) return false;
            ++col;
            break;
        case Direction::Up:
            if (row <= 0) return false;
            --row;
            break;
        case Direction::Down:
            if (row >= H - 1) return false;
            ++row;
            break;
    }
    return true;
}

bool Status::slide(Direction d){
    Position prev_blank = blank;
    if (blank.slide(d)){
        // post_process
        _update_after_slide(prev_blank);
        return true;
    }else{
        // can't slide
        return false;
    }
}

void Status::_update(){
    blank = find_blank(board);
    mhd = calc_MHD(board);
    key = calc_key(board);
}

void Status::_update_after_slide(const Position & prev_blank){
    auto prev_idx = pos2idx(prev_blank);
    auto new_idx = pos2idx(blank);
    auto panel_val = board[new_idx];
    
    // update Manhattan disntance
    // panel_val has moved from prev_blank to blank.
    int row_final = (panel_val - 1) / W;
    int col_final = (panel_val - 1) % W;
    // subtract the Manhattan distance from the previous position of panel_val,
    // which is the same as the current position of blank, to the final position of panel_val.
    mhd -= abs(row_final - blank.row) + abs(col_final - blank.col);
    // add the Manhattan distance from the current position of panel_val,
    // which is the same as the previous position of blank, to the final position of panel_val.
    mhd += abs(row_final - prev_blank.row) + abs(col_final - prev_blank.col);
    
    // swap 0 and panel_val on board
    board[prev_idx] = panel_val;
    board[new_idx] = 0;
    
    // update key
    // {prev_idx: 0, new_idx: panel_val} -> {prev_idx: panel_val, new_idx: 0};
    key -= (static_cast<unsigned long long>(panel_val)) << (4 * (WH - new_idx - 1));
    key += (static_cast<unsigned long long>(panel_val)) << (4 * (WH - prev_idx - 1));
    // if (key != calc_key(board)) cout << "key is wrong!\n " << key << endl << calc_key(board) << endl;
}

Measured memory_bytes: 180852