Snake

"Snake" is an arcade game played on a square field of size N \times N, divided into 1 \times 1 cells. Rows are numbered from $1$ to $N$ from top to bottom, and columns from $1$ to $N$ from left to right. Each cell has coordinates $(r,c)$, where $r$ denotes the row and $c$ the column.

At any moment, the snake occupies a sequence of adjacent cells, where each pair of consecutive cells shares a side. The tail of the snake is at the first cell of this sequence, and the head is at the last. Initially, both the tail and the head of the snake are at $(1,1)$, and each of the other cells contains either a berry or a mushroom.

On each turn, the snake can move its head in one of four directions: up, left, right, or down. If there is no cell in the chosen direction, or if the next cell contains a mushroom or a part of the snake's body, the snake dies and the game ends. If the next cell contains a berry, the snake eats it and lengthens by one cell. For example, at some moment in the game the snake may be positioned as:

In this situation, a move up or down causes the snake to die by colliding with its own body. A right move also results in death as there is a mushroom. The only possible move that does not result in death is left. After this move, the snake will be:

The objective of the player is to guide the snake so that it reaches the greatest length before dying. Schoolboy Vasya found playing "Snake" on his own uninteresting, so he developed an algorithm to control the snake. According to Vasya's algorithm, the first move is to the right if there is no mushroom to the right, or down otherwise (if there is a mushroom below, the snake dies after the first move). Afterwards, at each move, the snake tries to continue moving in the same direction as in the previous move. If this results in immediate death, it changes direction by turning $90$ degrees clockwise and moves in the new direction (even if this immediately results in death).

For example, suppose the field initially looks like this:

Following Vasya's algorithm, the snake will be positioned as shown just before it dies:

Vasya understands that his algorithm is not optimal. For instance, in the example above, the snake could have moved farther right to grow longer, but following Vasya's algorithm, it turns left and dies. Nevertheless, Vasya believes his algorithm is very good and allows the snake to reach great length.

Help Vasya verify his hypothesis by writing a program that simulates his algorithm. The program receives the field size $N$ and the positions of all mushrooms as input, and determines how many squares the snake occupies just before the move that results in its death if it follows Vasya's algorithm.