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

using namespace std;

// puzzle ?????¶?????????key (ULL) ??§??¨?????????
// priority_que ?????£????????????stack<key> pq[DPETH_LIMIT]; ????????????
// MHDsum ??????key ?????????????¨?????????????
// calc_MHD(int idx, int val) ?????????????¨???????????????¢????????????
// blank ???????????????key ?????????????¨?????????????
// key ???????¬?????????¢???????§????????¨????????????¢??°?????¨????????????

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 B = 4;
constexpr int WH = W * H;
constexpr unsigned long long key_goal = 1311768467463790320ull;
enum class Direction {Left, Right, Up, Down};

using Board = vector<int>;

using Key = unsigned long long;

Key calc_key(Board & board);

int calc_MHDsum(Key key);

int find_blank(Key key);

int MHD[WH][WH] = {{0}};

void init_MHD();

int calc_MHD(int idx, int val);

Key slide(Key key, int blank_idx, Direction d);

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

int solve(Key key_start);

////////////////////////////////////////////////
// main function
////////////////////////////////////////////////
int main()
{
    init_MHD();
    Board board(WH);
    cin >> board;
    Key key_start = calc_key(board);
    cout << solve(key_start) << endl;
    return 0;
}


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

int solve(Key key_start){
    stack<Key> pq[DEPTH_LIMIT + 1];
    map<Key, int> k2s;
    int fstar = 0 + calc_MHDsum(key_start);
    if (fstar == 0) return 0;
    pq[fstar].push(key_start);
    k2s[key_start] = 0;
    while (fstar <= DEPTH_LIMIT){
        if (pq[fstar].empty()){
            ++fstar;
            continue;
        }
        auto key = pq[fstar].top();
        pq[fstar].pop();
        int steps = fstar - calc_MHDsum(key);
        int next_steps = steps + 1;
        if (k2s[key] < steps) continue;
        int blank_idx = find_blank(key);
        for (auto d : {Direction::Left, Direction::Right, Direction::Up, Direction::Down}){
            auto new_key = slide(key, blank_idx, d);
            if (new_key){
                int new_fstar = next_steps + calc_MHDsum(new_key);
                if (new_fstar > DEPTH_LIMIT) continue;
                auto it = k2s.find(new_key);
                if (it == k2s.end() or it->second > next_steps){
                    k2s[new_key] = next_steps;
                    pq[new_fstar].push(new_key);
                    if (new_fstar < fstar) fstar = new_fstar;
                    if (new_key == key_goal) return next_steps;
                }
            }
        }
    }
    return -1;
}

Key calc_key(Board & board){
    Key key = 0ULL;
    for (auto val : board){
        key <<= B;
        key += val;
    }
    return key;
}

void init_MHD(){
    for (int idx = 0; idx != WH; ++idx){
        for (int val = 0; val != WH; ++val){
            MHD[idx][val] = calc_MHD(idx, val);
        }
    }
}

int calc_MHD(int idx, int val){
    if (val == 0) return 0;
    --val;
    int row_val = val / W;
    int col_val = val % W;
    int row_idx = idx / W;
    int col_idx = idx % W;
    return abs(row_val - row_idx) + abs(col_val - col_idx);
}

int calc_MHDsum(Key key){
    // Calculates the sum of Manhattan distances
    // from current position to goal position 
    // for all panels except blank (=0) panel. 
    int mhdsum = 0;
    int idx = WH;
    while (idx--){
        mhdsum += MHD[idx][key % WH];
        key >>= B;
    }
    return mhdsum;
}

int find_blank(Key key){
    // Find a blank (=0) panel on a board with width=W and height=H
    // and return its position (row, col).
    int idx = WH;
    while (idx--){
        if ((key % WH) == 0) return idx;
        key >>= B;
    }
}

Key slide(Key key, int blank_idx, Direction d){
    Key failure_code = 0ULL;
    int row = blank_idx / W;
    int col = blank_idx % W;
    int diff_idx = 0;
    switch(d){
        case Direction::Left:
            if (col == 0) return failure_code;
            diff_idx = -1;
            break;
        case Direction::Right:
            if (col == W - 1) return failure_code;
            diff_idx = 1;
            break;
        case Direction::Up:
            if (row == 0) return failure_code;
            diff_idx = -W;
            break;
        case Direction::Down:
            if (row == H - 1) return failure_code;
            diff_idx = W;
            break;
    }
    Key piece = key & (15ULL << ((WH - 1 - blank_idx - diff_idx)* B));
    key -= piece;
    if (diff_idx > 0){
        key += (piece << (diff_idx * B));
    }else{
        key += (piece >> (-diff_idx * B));
    }
    return key;
}

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

Measured memory_bytes: 91224