#include <cassert>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <queue>
#include <map>
typedef unsigned long long int TBoard;

/*
Index
0 1 2 3
4 5 6 7
8 9 A B
C D E F
0xFEDCBA9876543210L

Goal
1 2 3 4
5 6 7 8
9 A B C
D E F 0
0x0FEDCBA987654321L
*/
TBoard InputBoard(std::istream& in)
{
    TBoard Board = 0;
    for(int i = 0; i < 16; ++i){
        TBoard n;
        std::cin >> n;
        Board += n << (4*i);
    }
    return Board;
}
int GetEstimate(const TBoard& Board)
{
    const static int TableX[] = {3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2};
    const static int TableY[] = {3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3};
    int Cost = 0;
    for(int y = 0; y < 4; ++y){
        for(int x = 0; x < 4; ++x){
            int Value = (Board >> (4*(4*y+x))) & 0xF;
            if(Value == 0) continue;
            Cost += std::abs(x - TableX[Value]);
            Cost += std::abs(y - TableY[Value]);
        }
    }
    return Cost;
}
struct TState
{
    TBoard Board;
    int Cost;
    int Total;
    TState(const TBoard& ABoard, int ACost)
    : Board(ABoard), Cost(ACost), Total(ACost + GetEstimate(ABoard))
    {}
    bool operator<(const TState& State)const
    {
        return Total < State.Total;
    }
};
struct TGreater
{
    bool operator()(const TState& Left, const TState& Right)
    {
        return Left.Total >= Right.Total;
    }
};
int FindZero(const TBoard& Board)
{
    for(int i = 0; i < 16; ++i){
        if((Board & (0xFUL << (4*i))) == 0){
            return i;
        }
    }
    assert(false);
}
TBoard Swap(TBoard Board, int i, int j)
{
    assert(0 <= i && i < 16);
    assert(0 <= j && j < 16);
    TBoard MaskX = 0xFL << (i*4);
    TBoard MaskY = 0xFL << (j*4);
    TBoard x = (Board & MaskX) >> (i*4);
    TBoard y = (Board & MaskY) >> (j*4);
    Board &= ~MaskX;
    Board &= ~MaskY;
    Board |= x << (j*4);
    Board |= y << (i*4);
    return Board;
}
std::vector<TBoard> GetMoved(const TBoard& Board)
{
    int i = FindZero(Board);
    
    std::vector<TBoard> Result;
    if(i > 3){
        Result.push_back(Swap(Board, i, i-4));
    }
    if(i < 0xC){
        Result.push_back(Swap(Board, i, i+4));
    }
    if((i == 0 || i == 4 || i == 8 || i == 0xC) == false){
        Result.push_back(Swap(Board, i, i-1));
    }
    if((i == 3 || i == 7 || i == 0xB || i == 0xF) == false){
        Result.push_back(Swap(Board, i, i+1));
    }

    return Result;
}
void Print(const TBoard& Board, char c)
{
    for(int i = 0; i < 4; ++i){
        std::cerr << c;
        for(int j = 0; j < 4; ++j){
            std::cerr << ((Board >> ((i*4+j))*4) & 0xF) << " ";
        }
        std::cerr << std::endl;
    }
    std::cerr << std::endl;
}
int Solve(const TBoard& Start, const TBoard& Goal)
{
    std::priority_queue<TState, std::vector<TState>, TGreater> Open;
    std::map<TBoard, int> Table;
    Table[Start] = 0;
    Open.push(TState(Start, 0));

    while(!Open.empty()){
        TState State = Open.top();
        Open.pop();
        // Print(State.Board, ' ');
        // std::cerr << " Cost:" << State.Cost << ", Estimate:" << State.Total - State.Cost << ", Total:" << State.Total << std::endl;
        if(State.Board == Goal) return State.Cost;
        int Cost  = State.Cost + 1;
        std::vector<TBoard> Boards = GetMoved(State.Board);
        for(std::size_t i = 0; i < Boards.size(); ++i){
            const TBoard& Board = Boards[i];
            std::map<TBoard, int>::iterator It = Table.find(Board);
            if(It == Table.end() || Cost < It->second){
                Table[Board] = Cost;
                Open.push(TState(Board, Cost));
                // Print(Board, '\t');
            }
        }
    }
    assert(false);
}
int main()
{
    TBoard Goal = 0x0FEDCBA987654321L;
    TBoard Start = InputBoard(std::cin);
    std::cout << Solve(Start, Goal) << std::endl;
    return 0;
}

Measured memory_bytes: 88444