#include <iostream>
#include <istream>
#include <vector>

using namespace std;

// iterative deepening search

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, NA};

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, Direction prev_d);

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

int solve(Key key_start);

bool dfs(Key key, Direction prev_d, int depth, int limit);

////////////////////////////////////////////////
// main function
////////////////////////////////////////////////
int main()
{
    init_MHD();
    Board board(WH);
    cin >> board;
//    Board board{5, 1, 2, 4, 14, 9, 3, 7, 13, 10, 12, 6, 15, 11, 8, 0};
//    Board board{1, 6, 15, 0, 14, 11, 5, 7, 10, 9, 8, 3, 2, 13, 12, 4};
    Key key_start = calc_key(board);
    cout << solve(key_start) << endl;
    return 0;
}


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

int solve(Key key_start){
    int fstar = 0 + calc_MHDsum(key_start);
    for (int limit = fstar; limit != DEPTH_LIMIT + 1; ++limit){
        if (dfs(key_start, Direction::NA, 0, limit)){
            return limit;
        }
    }
    return -1;
}

bool dfs(Key key, Direction prev_d, int depth, int limit){
    if (key == key_goal) return true;
    auto blank_idx = find_blank(key);
    for (auto d : {Direction::Left, Direction::Right, Direction::Up, Direction::Down}){
        auto new_key = slide(key, blank_idx, d, prev_d);
        if (new_key){
            int new_fstar = 1 + depth + calc_MHDsum(new_key);
            if (new_fstar > limit) continue;
            if (dfs(new_key, d, depth + 1, limit)) return true;
        }
    }
    return false;    
}


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, Direction prev_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 or prev_d == Direction::Right) return failure_code;
            diff_idx = -1;
            break;
        case Direction::Right:
            if (col == W - 1 or prev_d == Direction::Left) return failure_code;
            diff_idx = 1;
            break;
        case Direction::Up:
            if (row == 0 or prev_d == Direction::Down) return failure_code;
            diff_idx = -W;
            break;
        case Direction::Down:
            if (row == H - 1 or prev_d == Direction::Up) return failure_code;
            diff_idx = W;
            break;
        case Direction::NA:
            return failure_code;
    }
    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: 3100