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.util.HashMap;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 

		n = 16;

		char[] s = new char[n];
		for (int i = 0; i < n; i++) {
			s[i] = (char)('0' + sc.nextInt());
		}
		
		ans = "123456789:;<=>?0";

		for (int i = 0; i < 46; i++) {
			hm = new HashMap<String, Integer>();
			limit = i;
			dfs(new Panel(toString(s), 0));
		}
		
        sc.close();
	}

	private static void dfs(Panel u) {
		if (u.s.equals(ans)) {
			System.out.println(u.count);
			System.exit(0);
		}
		
		if (u.count + u.min > limit) {
			return;
		}

		hm.put(u.s, u.count);
//		System.out.println(u + k);

		StringBuffer str = new StringBuffer(u.s);
		
		int zero = str.indexOf("0");
		assert (zero != -1);
		for (int i = 0; i < d.length; i++) {
			if (zero + d[i] >= 0 && zero + d[i] < n && !(d[i] == -1 && (zero + d[i]) % 4 == 3) && !(d[i] == 1 && (zero + d[i]) % 4 == 0)) {
				str.setCharAt(zero, str.charAt(zero + d[i]));
				str.setCharAt(zero + d[i], '0');
				String tmps = str.toString();
				if (!hm.containsKey(tmps) || hm.get(tmps) > u.count + 1) {
					dfs(new Panel(tmps, u.count + 1));
				}
				str.setCharAt(zero + d[i], str.charAt(zero));
				str.setCharAt(zero, '0');
			}
		}
	}

	private static int n;
	private static int limit;
	private static String ans;
	private static final int[] d = {4, -4, -1, 1};
	
	private static HashMap<String, Integer> hm;

	private static class Panel {
		String s;
		int count;
		int min;
		
		Panel (String s, int count) {
			this.s = s;
			this.count = count;
			this.min = getMin(s);
		}
		
		private int getMin(String s) {
			char[] c = s.toCharArray();
			int ret = 0;
			for (int i = 0; i < c.length; i++) {
				int tmp = c[i] - '0';
				if (tmp != 0) {
					int x = (tmp - 1) % 4;
					int y = (tmp - 1) / 4;
					ret += Math.abs(x - i % 4) + Math.abs(y - i / 4);
				}
			}
			
			return ret;
		}

	}

	private static String toString(char[] s) {
		String ret = "";
		for (int i = 0; i < s.length; i++) {
			ret += s[i];
		}
		
		return ret;
	}
}