Queens

On 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₁, q₂, …, q_k such that queen A captures queen q₁, queen q_i captures queen q_i + 1 (1 ≤ i < k), and queen q_k captures queen B.

Input Specification

The 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⁹, 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 Specification

For each test case, the program has to write out into a separate line the number of groups the queens form.

Sample Input

1. 2
2. 8 5
3. 0 0
4. 2 4
5. 5 4
6. 0 2
7. 6 3
8. 8 3
9. 2 1
10. 3 6
11. 7 5

download as text file

Output for Sample Input

1. 1
2. 3

download as text file