Game Moves

2048 is a puzzle game in which you slide numbered tiles on a square grid and combine equal tiles into tiles of larger and larger value. The original aim is to make a 2048 tile, but the game continues until no move is possible, whether or not a 2048 tile has been made. The game starts with two tiles on random squares of an empty board, each with value 2 or 4.

The game proceeds as a series of moves, and every move has five phases: choice of direction, movement, merging, gap closing, and birth.

1. Choice of direction: the player chooses up, down, left or right. The chosen direction is called downstream.
2. Movement: the player moves all tiles downstream as far as they will go, closing any gaps. The edge of the board that the tiles move toward is called the blocking edge.
3. Merging: working upstream, away from the blocking edge, a tile that has the same value as its upstream neighbor merges with it into a single tile whose value is the sum of the two. A tile produced by a merge takes no further part in merging during the same move. Each merge increases the score by the value of the new tile.
4. Gap closing: all tiles move downstream again as far as they will go, closing any gaps.
5. Birth: a new tile with value 2 or 4 appears on an empty square. The value and the square are both random.

The board must change in some way during the second or third phase for the move to be valid, and only then does a new tile appear.

The score starts at zero and increases by the value of the new tile whenever two tiles combine. The game is usually played on a $4 \times 4$ grid, and square grids of other sizes are also used.

(a) Score is 16

(b) Down, score is 24

(c) Down, score is 32

(d) Down, score is 48

Figure 1: score progression for a series of moves. New values are shown in blue.

Figure 1 shows a progression of moves with the score going from 16 to 24 to 32 to 48. The progression starts with Figure 1(a), which has been reached after seven moves. The player uses a Down move and the two vertical pairs of 2s in the third and fourth columns merge to become 4s. Because two 4s are generated, the score increases by 8. The resulting board is Figure 1(b), with a new 2 randomly appearing in the second column. The player uses a second Down move and the vertical pair of 4s in the fourth column merges to become an 8. The score increases by the sum of the merged values, that is by 8. The board becomes Figure 1(c), with a new 4 randomly appearing in the fourth column. Finally the player moves Down again and the vertical pair of 8s in the fourth column merges to become a 16, which increases the score by 16. The resulting board is Figure 1(d).

(a) Current state

(b) After move Right

(c) After move Left

Figure 2: how values merge and move

Figure 2 is demonstrative and shows how values merge and move. This demonstration does not show any new values appearing on the board. Assume the game board is in the state shown in Figure 2(a). If the player moves Right, the two horizontal pairs of 2s in the bottom row merge to become 4s as shown in Figure 2(b), while in the top row only the rightmost pair of 4s merges to become an 8. If the player then moves Left, the horizontal pair of 4s in the bottom row merges into a single 8 as shown in Figure 2(c), and the values in the top row move but do not merge.

Given the state of a game and the current score, write a program that determines the number of moves it has taken to reach that state.

The first line contains the size of the square grid, $n$ ($2 \le n \le 7$).

The next $n$ lines each contain $n$ space separated integers describing the current state of a game. A value of 0 marks an empty square. Every non-empty square holds a power of two between 2 and $2^{50}$, inclusive.

The last line contains the score $s$ for the current state ($0 \le s \le 108086391056891712$).

Every input is a state that a real game can reach.

Print the number of moves it has taken to reach the current state of the game. The answer is less than $2^{63}$.