Painters' Duel

A new art museum is about to open! It is a single-story building in the shape of a large equilateral triangle. The triangle is made up of many smaller identical equilateral-triangle-shaped rooms, and the side length of the museum is $S$ times the side length of one room. Each room has doors connecting it to every other room with which it shares a side (not just a vertex).

Each room is identified by two numbers: the row of the building it is in (counting from top to bottom, starting from 1), followed by its position within that row (counting from left to right, starting from 1). Here is an example of how the rooms are connected and labeled when $S=3$:

Alma and Berthe are artists who are painting the rooms of the museum. Alma starts in the room $(R_A, P_A)$, and Berthe starts in a different room $(R_B, P_B)$. Each of them has already painted their starting room. $C$ of the other rooms are under construction, and neither Alma nor Berthe is allowed to enter these rooms or paint them.

Alma and Berthe play a turn-based game, with Alma starting first. On a painter's turn, if their current room is adjacent to at least one unpainted room that is not under construction, the painter must choose one of those rooms, move to it, and paint it. Otherwise, the painter cannot move and does nothing on their turn. Once both painters are unable to move, the game is over. The score of the game is the number of rooms painted by Alma minus the number of rooms painted by Berthe.

Both painters make optimal decisions. Alma tries to maximize the score, and Berthe tries to minimize it. Determine the best score Alma can guarantee, regardless of what Berthe does.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each case begins with one line containing six integers $S$, $R_A$, $P_A$, $R_B$, $P_B$, and $C$. These are the side length of the museum (as a multiple of the side length of a room), the row and position of Alma's starting room, the row and position of Berthe's starting room, and the number of rooms under construction. Then, there are $C$ more lines. The $i$-th of these lines contains two integers $R_i$ and $P_i$, the row and position of the $i$-th room under construction.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the best score that Alma can guarantee.

• $0 \le C \le S^2 - 2$.
• $1 \le R_A \le S$.
• $1 \le P_A \le 2R_A - 1$.
• $1 \le R_B \le S$.
• $1 \le P_B \le 2R_B - 1$.
• $(R_A, P_A) \ne (R_B, P_B)$.
• $1 \le R_i \le S$, for all $i$.
• $1 \le P_i \le 2R_i - 1$, for all $i$.
• $(R_i, P_i) \ne (R_A, P_A)$, for all $i$.
• $(R_i, P_i) \ne (R_B, P_B)$, for all $i$.
• Either $R_i < R_{i+1}$, or $R_i = R_{i+1}$ and $P_i < P_{i+1}$, for all $i < C$.

In Sample Case #1, the turns must proceed as follows:

1. Alma moves to room (2, 2).
2. Berthe cannot move.
3. Alma moves to room (2, 3).
4. Berthe still cannot move.
5. Alma cannot move. Since neither painter can move, the game is over.

Alma has painted 3 rooms and Berthe has painted 1 room, so the score is 3 - 1 = 2.

In Sample Case #2, neither painter can move. They only paint their starting rooms.

The following additional cases could not appear in Test Set 1, but could appear in Test Set 2.

2
3 3 4 2 1 2
2 3
3 1
3 3 2 2 3 2
2 1
3 1

The correct output for these two cases would be:

Case #1: 0
Case #2: -1

In Case #1, Alma can move to (3, 5) or (3, 3). She cannot move to (2, 3), which is under construction.

• If she moves to (3, 5), she has no more moves, and Berthe goes on to paint two more rooms. Score: 2 - 3 = -1.
• If Alma moves to (3, 3), Berthe can either move to (3, 2), which leaves neither painter with any future moves (score: 2 - 2 = 0), or move to (2, 2). In the second case, Alma moves to (3, 2) and Berthe moves to (1, 1), giving a score of 3 - 3 = 0.

Alma knows that moving to (3, 3) guarantees a score of 0 no matter what Berthe does, which is better than the score of -1 from moving to (3, 5). Therefore, Alma moves to (3, 3). We do not know exactly how the rest of this game plays out, but we know the best score Alma can guarantee. It is possible that one or more rooms that are not under construction never get painted.

In Case #2, Alma must move to (3, 3), and then it is better for Berthe to move to (3, 4) than to (2, 2).