Opening a Restaurant

You want to open a new restaurant. The city is an $M \times M$ grid. Every road is either vertical or horizontal, and the roads in each direction are numbered from $0$ to $M-1$. Every restaurant sits at an intersection, and an intersection is written as a coordinate $(x, y)$, the pair (vertical road number, horizontal road number). The distance between two intersections $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

The city has two large apartment buildings $A$ and $B$ that lie on the same horizontal road (that is, they share the same $y$ coordinate). Both apartments already have a restaurant.

Because the residents of the two apartments meet often, you want to place the new restaurant somewhere between them. However, once the existing restaurants and rent are taken into account, the exact midpoint is not always best. So you look for a "good place" defined as follows, where $\text{dist}(p, q)$ is the distance between $p$ and $q$.

An intersection $p$ is a "good place" if, for every existing restaurant $q$, $\text{dist}(p, A) < \text{dist}(q, A)$ or $\text{dist}(p, B) < \text{dist}(q, B)$. In other words, $p$ is not a good place if there is any restaurant $q$ that satisfies $\text{dist}(p, A) \ge \text{dist}(q, A)$ and $\text{dist}(p, B) \ge \text{dist}(q, B)$ at the same time.

The restaurants $q$ that are compared include the ones at the two apartments $A$ and $B$.

For example, consider an $11 \times 11$ city with apartments $A = (0, 5)$ and $B = (10, 5)$.

• $(7, 4)$ is a good place.
• $p = (4, 6)$ is not a good place because of the restaurant $q = (3, 5)$ (here $\text{dist}(p, A) = 5 \ge \text{dist}(q, A) = 3$ and $\text{dist}(p, B) = 7 \ge \text{dist}(q, B) = 7$).
• $(0, 0)$ is not a good place because of the restaurant at apartment $A = (0, 5)$.

Given the positions of the existing restaurants, count how many of the $M \times M$ intersections of the city are good places.

The first line contains the number of test cases $T$. For each test case, the first line contains the city size $M$ and the number of restaurants $N$ ($2 \le M \le 60000$, $2 \le N \le 50000$). Each of the next $N$ lines contains the coordinates $x_i$, $y_i$ of a restaurant ($0 \le x_i, y_i < M$).

No two restaurants share the same coordinates. Apartment $A$ is at the first restaurant and apartment $B$ is at the second restaurant, and $A$ and $B$ lie on the same horizontal road.

For each test case, print the number of good places on its own line.