Problem: The goal of the 15 puzzle problem is to complete pieces on $4 \times 4$ cells where one of the cells is empty space.

In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 15 as shown below.


1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).


1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0


Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Constraints

* The given puzzle is solvable in at most 45 steps.

Input

The $4 \times 4$ integers denoting the pieces or space are given.

Output

Print the fewest steps in a line.

Example

Input

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


Output

8

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main {
    // static int time = 0;
 
    public static void main(String[] args) throws IOException {
 
        Scanner scan = new Scanner(System.in);
        // Scanner scan = new Scanner(new
        // File("D:\\UserArea\\J0124567\\Downloads\\ALDS1_6_A-in9.txt"));
 
        HS hs = new HS();
 
        for (int y = 0; y < 4; y++)
            for (int x = 0; x < 4; x++)
                hs.SetIni(x, y, scan.nextInt());
 
        System.out.println(hs.solve());
 
        scan.close();
        System.exit(0);
    }
}
 
class HS {
    class Bd {
        byte[][] pn = new byte[4][4];
        int oper = 0;
        int diff = 0;
 
        public long getKey() {
            long key = 0;
            for (int x = 0; x < 4; x++)
                for (int y = 0; y < 4; y++) {
                    key *= 10;
                    key += pn[x][y];
                }
            return key;
        }
 
        public int eval() {
            int ret = 0;
            for (int x = 0; x < 4; x++)
                for (int y = 0; y < 4; y++) {
                    int p = pn[x][y];
                    if (p != 0)
                        ret += Math.abs(x - gx[p]) + Math.abs(y - gy[p]);
                }
            diff = ret;
            return ret;
        }
 
        public void copy(Bd b) {
            for (int x = 0; x < 4; x++)
                for (int y = 0; y < 4; y++)
                    pn[x][y] = b.pn[x][y];
            diff = b.diff;
            oper = b.oper;
        }
 
        private boolean up() {
            for (int x = 0; x < 4; x++)
                for (int y = 0; y < 3; y++)
                    if (pn[x][y] == 0) {
                        pn[x][y] = pn[x][y + 1];
                        pn[x][y + 1] = 0;
                        oper++;
                        eval();
                        return true;
                    }
            return false;
        }
 
        private boolean down() {
            for (int x = 0; x < 4; x++)
                for (int y = 1; y < 4; y++)
                    if (pn[x][y] == 0) {
                        pn[x][y] = pn[x][y - 1];
                        pn[x][y - 1] = 0;
                        oper++;
                        eval();
                        return true;
                    }
            return false;
        }
 
        private boolean right() {
            for (int x = 1; x < 4; x++)
                for (int y = 0; y < 4; y++)
                    if (pn[x][y] == 0) {
                        pn[x][y] = pn[x - 1][y];
                        pn[x - 1][y] = 0;
                        oper++;
                        eval();
                        return true;
                    }
            return false;
        }
 
        private boolean left() {
            for (int x = 0; x < 3; x++)
                for (int y = 0; y < 4; y++)
                    if (pn[x][y] == 0) {
                        pn[x][y] = pn[x + 1][y];
                        pn[x + 1][y] = 0;
                        oper++;
                        eval();
                        return true;
                    }
            return false;
        }
 
        public boolean move(int op) {
            switch (op) {
            case (0):
                return up();
            case (1):
                return down();
            case (2):
                return right();
            case (3):
                return left();
            }
            return false;
        }
 
        public boolean isSame(Bd b) {
            for (int x = 0; x < 4; x++)
                for (int y = 0; y < 4; y++)
                    if (b.pn[x][y] != pn[x][y])
                        return false;
            return true;
        }
    }
 
    private Bd bd = new Bd();
    private int[] gx = { 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2 };
    private int[] gy = { 3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3 };
    // private ArrayList<Bd> hist = new ArrayList<Bd>();
    private Map<Long, Integer> hist = new HashMap<>();
    private PriorityQueue<Bd> pqueue = new PriorityQueue<Bd>(3, new Qcomparator());
 
    class Qcomparator implements Comparator<Bd> {
        @Override
        public int compare(Bd b1, Bd b2) {
            if (b1.diff + b1.oper > b2.diff + b2.oper)
                return 1;
            else if (b1.diff + b1.oper == b2.diff + b2.oper)
                return 0;
            else
                return -1;
        }
    }
 
    public void SetIni(int x, int y, int a) {
        bd.pn[x][y] = (byte) a;
    }
 
    public int solve() {
        Bd b = new Bd();
        b.copy(bd);
        b.eval();
        pqueue.add(b);
        hist.put(b.getKey(), 0);
        return search();
    }
 
    private int search() {
        while (true) {
            Bd b = pqueue.poll();
            if (b == null)
                return -1;
 
            // printBd(b);
 
            if (b.diff == 0)
                return b.oper;
 
            for (int i = 0; i < 4; i++) {
                Bd nb = new Bd();
                nb.copy(b);
                if (nb.move(i))
                    addQueue(nb);
            }
        }
    }
 
    private boolean addQueue(Bd b) {
        long k = b.getKey();
        if (hist.containsKey(k)) {
            int oper = hist.get(k);
            if (oper > b.oper) {
                hist.put(k, b.oper);
                pqueue.add(b);
                return true;
            } else
                return false;
        }
        hist.put(k, b.oper);
        pqueue.add(b);
        return true;
    }
 
    /*private void printBd(Bd b) {
        System.out.println("----------------");
        for (int y = 0; y < 3; y++)
            System.out.println("- " + b.pn[0][y] + " " + b.pn[1][y] + " " + b.pn[2][y] + " -");
        System.out.println("------- diff " + b.diff + " oper " + b.oper + " queue " + pqueue.size());
        if (pqueue.size() > 100000)
            System.exit(0);
    }*/
}