//#define debug //*******************************************************************************************************************************************

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [Tips]
// XCode??§???EOF??\??????Ctrl+D
// ?\???Alt+\
// ans???????§?INT?????????2,147,483,647????¶????????????¨??????????????§long long?????£???????????????????????????
// ????????°??¨??? = dout << static_cast<bitset<8> >(x)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////




////////////////////////////////////////
//15 Puzzle
//??????????????????ID-DFS (Iterative Deepening Depth-First Search) ??????
//yukicorder???No.585 ??\????????????????????????????????????????????????????????£??? (??¬?§£??????ad???hoc?§£????????£????????§) ??¨?????????????????????????????§???
//15???????????????????????£???????£????????????? (????????¬????????????)
////////////////////////////////////////


#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter
#include <set>


//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILE???.
//#define INPUTFILE "input.txt" //**************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scand(A) scanf("%d", &(A))
#define scans(A) scanf("%s", (A))
#define printd(A) dout << "%d\n", (A))
#define prints(A) dout << "%s\n", (A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl
#define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl
#define line  dout << "----------------\n"
#define line2 dout << "================\n"

#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) ((i)/2)
#define l(i) ((i)*2)
#define r(i) ((i)*2+1)
#define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16)
#define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1
#define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0


typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

//const int INF = (1LL<<31)-1;
const int NONE = -1;
//const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
//const ull INF_ULL = (ull)1e19-1ULL;
//#define MOD 1000000007 //??§???????´???°?????£??¨??¨????????°????????????10???7??????

#define N_MAX 3 //num of vertex or element
//#define M_MAX 124760 //num of edge
//#define DATA_MAX 1010

#define N 4
#define N2 16

char dir[4] = {'U','L','R','D'}; //0??¨3???1??¨2??????????????????????¶??????????move (??????3?????¨??????????¶??????????)
int dx[4] =   {-1,  0,  0,  1 };
int dy[4] =   { 0, -1,  1,  0 };

int MDT[N2][N2]; //Manhattan Distance Table
                 //MDT[i][j] = ????????°???i?????????j???????????¨?????????i?????£?????????????????§???MD (i=0????????????????????????0)

#define LIMIT_MAX 50 //ID-DFS????????§??±?????¶??? (100?????\???????????????????????????????§£????????§?????????)
int LIMIT; //?????¨?????±?????¶???
int path[LIMIT_MAX]; //GOAL?????§????????????????????????????????????????????????????¨??????¨???path[i] = ???cost i????????????????????????cost i+1??????????????????????§?????????¨????????????k

ll numOfSearch = 0; //??¢?´¢?????°


struct PUZZLE {
    int state[N2];
    int space; //state[space] = 0
    int cost; //????????¶??????????????¨??¶????????§????§?????????????????????????????????°
    int md; //manhattan distance to GOAL (GOAL?????§????§?????????????????????§????????????????????°??????????????¨???????????\??????????????£??????????¨?)
            //???????????£??? cost + md > LIMIT ??§????????°??????????????§??????
    
    
    bool isGoal() {
        rep(i,0,N2) {
            if(i!=N2-1 and state[i]!=i+1) return false;
            if(i==N2-1) assert(state[i]==0);
        }
        return true;
    }
    
    
    int calcMD() {
        int sum = 0;
        
        rep(i,0,N2) {
            sum += MDT[state[i]][i];
        }
        
        return md = sum;
    }
    
    
    
    
    void display() {
#ifdef debug
        line;
//        char s[N+1];
        show(state, 0, N2);
        
        rep(i,0,N) {
            rep(j,0,N) {
//                if(state[i*N+j]<10) s[j] = state[i*N+j] + '0';
//                else s[j] = state[i*N+j] - 10 + 'A';
                
                disP(state[i*N+j]);
                
            }
            dout << "\n";
            
//            s[N] = '\0';
//            prints(s);
        }
        dout << "\n";
        
        dout << "space = " << space << "\n";
        dout << "cost = " << cost << "\n";
        dout << "md = " << md << "\n";
        line;
#endif
    }
    
    
    
    
    bool rotate(int k) { //k?????? (k = 0, 1, 2, 3) ???move????????????true????????????????????????0?????????????£?????????????????????????????§????????????????false?????????
                         //???????????????????????????????????°?????´??°?????????
        assert(0<=k and k<=3);
        assert(0<=space and space<N2);
        
        int current_space_x = space/N;
        int current_space_y = space%N;
        
        int next_space_x = current_space_x + dx[k];
        int next_space_y = current_space_y + dy[k];
        
        if(0<=next_space_x and next_space_x<N and 0<=next_space_y and next_space_y<N ) {
            int next_space = next_space_x * N + next_space_y;
            
            int moveNumber = state[next_space];
            swap(state[space], state[next_space]);
            
            //update other member variables
            md -= MDT[moveNumber][next_space];
            md += MDT[moveNumber][space];
            space = next_space;
            cost++;
            
            return true;
            
        }
        
        else return false;
        
    }
    
} puzzle; //?????¨??????????????????????????? (??????????????¶???)




void init() {
    
    //initiailize MDT[][]
    rep(i,0,N2) {
        rep(j,0,N2) {
            if(i==0) MDT[i][j] = 0;
            else MDT[i][j] = abs((i-1)/N - j/N) + abs((i-1)%N - j%N);
        }
    }
   
}



void display() {
#ifdef debug
    line;
   
#endif
}




bool dfs(int moveHistory[3]) { //??´??????3???????????°??§??????????????????????????´??????NONE?????\??£?????????????????????NONE=-1??????????????????????????????????????????????????????
    
    numOfSearch++;
    
#ifdef debug
    dout << "========================= dfs( " << moveHistory[2] << ", " << moveHistory[1] << ", " << moveHistory[0] << " )\n";
    disp(numOfSearch);
    puzzle.display();
#endif
    
    if( puzzle.isGoal() ) {
#ifdef debug
        dout << "GOAL??¨?????´???????????§true?????????\n";
#endif
        
        return true;
    }
    
    if( puzzle.cost + puzzle.md > LIMIT ) { //???????????§?????????????????´???????????§?????¨???????????? (?????????) ????????¨?????±?????¶???????¶???????????????¢?´¢???????????????
                                            //(?????¨?????±?????¶?????§??????????????£????????´???????????????????????????????????¨???????????¨????????§)
#ifdef debug
        dout << "puzzle.cost = " << puzzle.cost << " + puzzle.md = " << puzzle.md << " ???????????¨???LIMIT = " << LIMIT << " ????¶????????????§???????????\??????????????????false?????????\n";
#endif
        return false;
    }
    
    
    //recursive call for 4 move
#ifdef debug
        dout << "??????????????????1?????§????§???§???????????????????????????dfs????????°??????????????????????????? (?????§4???)\n\n";
#endif
    
    PUZZLE backup = puzzle; //for track back
    
    rep(k,0,4) {
        
        puzzle = backup; //???k??§puzzle????????¢????????????????????§???k???loop?????¨???puzzle???????????¶??????????????????
        
#ifdef debug
        line;
        dout << "k = " << k << " : " << dir[k] << "\n";
#endif
        
        if( moveHistory[0] + k == N-1 ) {
#ifdef debug
            dout << "??´??????1??? " << moveHistory[0] << " ??????????¶?????????????????????§???continue\n";
#endif
            continue;
        }
        
        
//        if( moveHistory[0]!=k and moveHistory[1]+k==N-1 and moveHistory[0]+moveHistory[2]==N-1 ) {
//#ifdef debug
//            dout << "??´??????3??? (" << moveHistory[2] << ", " << moveHistory[1] << ", " << moveHistory[0] << ") ??¨???????????????1??¨????????????????????§???continue\n";
//#endif
//            continue;
//        }
        
        
        
        //move k ?????????
        bool rotateResult = puzzle.rotate(k);
        if(rotateResult==false) {
#ifdef debug
            dout << "??????move???????????§??????????????§???continue\n";
#endif
            continue;
        }
        
        int hist_new[3];
        hist_new[2] = moveHistory[1];
        hist_new[1] = moveHistory[0];
        hist_new[0] = k;
        
        if( dfs(hist_new) ) {
#ifdef debug
            dout << "------------------ end of ------------------ dfs( " << moveHistory[2] << ", " << moveHistory[1] << ", " << moveHistory[0] << " )\n";
            dout << "????¨????dfs????????????????????¨??????puzzle?????\???\n";
            backup.display();
            dout << "????????????true????????£??????????????§???GOAL?????§?????????????????????????????£??????\n";
            dout << "????????? k = " << k << " (" << dir[k] << ") ??? path[ cost = " << backup.cost << " ] ???????????????\n";
            dout << "--------- END ---------\n";
#endif
            
            path[backup.cost] = k;
            
            return true;
        }
        
        
    } //end of k-loop
    
    
    //4 move ???????????????????????????true????????£??????????????£??????false?????????
    return false;
    
}





int solve_iterativeDeepening(PUZZLE in) {
    
    
    for(LIMIT=in.calcMD(); LIMIT<=LIMIT_MAX; LIMIT++) {
        
#ifdef debug
        dout << "//////////////////////// LIMIT = " << LIMIT << " ////////////////////////////////////\n";
#endif
        
        puzzle = in; //track back to initial state
        int moveHistory[3] = {NONE, NONE, NONE};
        
        //call dfs
        if( dfs(moveHistory) ) {
            return puzzle.cost;
        }
        
    }
    
    return NONE;
}







int main() {
    
    //cin, cout????????????  ?????¨??????cin?????????????????¨??¨cin??§???scanf?????????????????¨??¨scanf??§??±?????????????????????
    cin.tie(0); //cin??¨cout??????????????????
    ios::sync_with_stdio(false); //iostream??¨stdio??????????????????
    
    //read input data
    //    scand(N);
    
    rep(i,0,N) {
        rep(j,0,N) {
            scand(puzzle.state[i*N+j]);
            if(puzzle.state[i*N+j]==0) puzzle.space = i*N + j;
        }
    }
    
    
    
    //------------------------------------------------------------------------------------------
    #ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
    #endif
    //------------------------------------------------------------------------------------------
    
    
    
    init();
    
    int ans = solve_iterativeDeepening(puzzle);
    
    
    
#ifdef debug
    dout << "=== OUTPUT ===\n";
#endif
    
    dout << ans << endl;
    
    
#ifdef debug
    dout << "?????????????????????\n";
    show(path, 0, LIMIT_MAX);
    show(path, 0, ans);
    
    dout << "solution = ";
    rep(i,0,ans) disP(dir[path[i]]);
    dout << endl;
#endif
     
#ifdef OUTPUTFILE
    cout << "ans = " << ans << endl;
    cout << "numOfSearch = " << numOfSearch << endl;
    cout << "?????????????????????\n";
    
    cout << "solution = ";
    rep(i,0,ans) cout << dir[path[i]] << " ";
    cout << endl;
#endif
    
    
    
    
    //------------------------------------------------------------------------------------------
    #ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
    #ifdef OUTPUTFILE
    cout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
    #endif
    #endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}

Measured memory_bytes: 3268