음식점 개업

당신은 새 음식점을 개업하려고 한다. 도시는 크기가 $M \times M$인 격자로 나타낼 수 있다. 모든 도로는 수직 또는 수평이고, 각 방향의 도로에는 $0$번부터 $M-1$번까지 번호가 매겨져 있다. 모든 음식점은 교차로에 있으며, 교차로는 (수직 도로 번호, 수평 도로 번호) 쌍인 좌표 $(x, y)$로 나타낸다. 두 교차로 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.

도시에는 큰 아파트가 두 개 있고, 두 아파트 $A$와 $B$는 같은 수평 도로 위에 있다(즉 $y$ 좌표가 같다). 두 아파트에는 이미 음식점이 있다.

두 아파트에 사는 사람들이 자주 만나기 때문에, 당신은 새 음식점을 두 아파트 사이의 알맞은 자리에 두려고 한다. 하지만 이미 있는 음식점과 임대료를 고려하면 정중앙이 항상 가장 좋은 것은 아니다. 그래서 다음 조건을 만족하는 "좋은 곳"을 찾으려고 한다. 여기서 $\text{dist}(p, q)$는 $p$와 $q$ 사이의 거리이다.

교차로 $p$가 "좋은 곳"이 되려면, 이미 있는 모든 음식점 $q$에 대해 $\text{dist}(p, A) < \text{dist}(q, A)$ 또는 $\text{dist}(p, B) < \text{dist}(q, B)$를 만족해야 한다. 바꿔 말하면, $\text{dist}(p, A) \ge \text{dist}(q, A)$이면서 동시에 $\text{dist}(p, B) \ge \text{dist}(q, B)$인 음식점 $q$가 하나라도 있으면 $p$는 "좋은 곳"이 아니다.

비교 대상 $q$에는 두 아파트 $A$, $B$에 있는 음식점도 포함된다.

예를 들어 아파트가 $A = (0, 5)$, $B = (10, 5)$인 $11 \times 11$ 도시를 생각하자.

• $(7, 4)$는 "좋은 곳"이다.
• $p = (4, 6)$은 음식점 $q = (3, 5)$ 때문에 "좋은 곳"이 아니다. ($\text{dist}(p, A) = 5 \ge \text{dist}(q, A) = 3$이고 $\text{dist}(p, B) = 7 \ge \text{dist}(q, B) = 7$)
• $(0, 0)$은 아파트 $A = (0, 5)$에 있는 음식점 때문에 "좋은 곳"이 아니다.

이미 있는 음식점들의 위치가 주어졌을 때, 도시의 모든 교차로 $M \times M$개 중 "좋은 곳"의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 도시의 크기 $M$과 음식점의 수 $N$이 주어진다($2 \le M \le 60000$, $2 \le N \le 50000$). 이어지는 $N$개의 줄에는 각 음식점의 좌표 $x_i$, $y_i$가 주어진다($0 \le x_i, y_i < M$).

두 음식점의 좌표가 같은 경우는 없다. 아파트 $A$는 첫 번째 음식점, 아파트 $B$는 두 번째 음식점의 위치에 있으며, $A$와 $B$는 같은 수평 도로 위에 있다.

각 테스트 케이스마다 "좋은 곳"의 개수를 한 줄에 하나씩 출력한다.