

QueensOn the chessboard, the queen is able to move any number of squares vertically, horizontally, or diagonally (see the figure). Queen A captures queen B if queen A can move to the square of queen B in one step.
There is an N × N chessboard, and there are Q pieces of queens on it. The task is to count how many groups the queens form. Queen A and queen B belong to the same group if they capture each other or there are queens q_{1}, q_{2}, …, q_{k} such that queen A captures queen q_{1}, queen q_{i} captures queen q_{i + 1} (1 ≤ i < k), and queen q_{k} captures queen B. Input SpecificationThe first line of the input contains the number of test cases t (1 ≤ t ≤ 100). The first line of each test case contains two positive integers: N is the size of the chessboard, and Q is the number of queens (1 ≤ N ≤ 10^{9}, 1 ≤ Q ≤ min {N × N, 1000}). The next Q lines contain the (x_{i}, y_{i}) coordinates of the queens (0 ≤ x_{i}, y_{i} ≤ N – 1, 1 ≤ i ≤ Q). There are no two or more queens on the same square. Output SpecificationFor each test case, the program has to write out into a separate line the number of groups the queens form. Sample Input
Output for Sample Input


University of Debrecen; Faculty of Informatics; v. 03/01/2019 