Mr. Kim is planning to open a new restaurant. His city is laid out as a grid with size M × M . Therefore, every road is horizontal or vertical and the horizontal roads (resp., the vertical roads) are numbered from 0 to M − 1. For prof- itability, all restaurants are located near road junctions. The city has two big apartments which are located on the same horizontal road. The figure below shows an example of a city map with size 11 × 11. A circle represents an exist- ing restaurant and a circle labeled with ‘A’ or ‘B’ represents the location of an apartment. Notice that a restaurant is already located at each apartment. Each road junction is represented by the coordinate of the ordered pair of a ver- tical road and a horizontal road. The distance between two locations (x1, y1) and (x2, y2) is computed as |x1 − x2| + |y1 − y2|. In the figure below, the coordinates of A and B are (0, 5) and (10, 5), respectively. Mr. Kim knows that the residents of the two apartments frequently have a meeting. So, he thinks that the best location of a new restaurant is halfway between two apartments. Considering lease expenses and existing restaurants, however, he can’t select the optimal location unconditionally. Hence he decides to regard a location satisfying the following condition as a good place. Let dist(p, q) be the distance between p and q. A location p is a good place if for each existing restaurant’s location q, dist(p, A) < dist(q, A) or dist(p, B) < dist(q, B). In other words, p is not a good place if there exists an existing restaurant’s location q such that dist(p, A) ≥ dist(q, A) and dist(p, B) ≥ dist(q, B). In the above figure, the location (7,4) is a good place. But the location p = (4,6) is not good because there is no apartment which is closer to p than the restaurant at q = (3, 5), i.e., dist(p, A) = 5 ≥ dist(q,A) = 3 and dist(p,B) = 7 ≥ dist(q,B) = 7. Also, the location (0,0) is not good due to the restaurant at (0,5). Notice that the existing restaurants are positioned regardless of Mr. Kim’s condition. Given n locations of existing restaurants, write a program to compute the number of good places for a new restaurant. Input Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers M and n (2 ≤ M ≤ 60,000 and 2 ≤ n ≤ 50,000), which represent the size of a city map and the number of existing restaurants, respectively. The (i + 1)-th line of a test case contains two integers xi and yi (i = 1,2,...,n and 0 ≤ xi,yi < M), which represents the coordinate of the i-th existing restaurant. Assume that all restaurants have distinct coordinates and that the two apartments A and B are positioned at the locations of 1-st restaurant and 2-nd restaurant. Notice that A and B are placed on the same horizontal line.
2/2 Output Your program is to write to standard output. Print exactly one line for each test case. Print the number of good places which can be found in a given city map. The following shows sample input and output for two test cases. Sample Input 2 63 13 43 02 11 11 05 10 5 49 28 78 56 35 53 32 72 91 Sample Output 2 16