Treasure Hunt

You are given a grid with a number of treasure locations. Two treasures at positions \( (x_1, y_1) \) and \( (x_2, y_2) \) are considered adjacent if \( |x_1 - x_2| \le 1 \) and \( |y_1 - y_2| \le 1 \). Your task is to choose a subset of these treasures such that no two of them are adjacent, and the number of chosen treasures is maximized.

For example, if there are treasures at coordinates (1, 1), (1, 3), (2, 2), and (4, 4) on a 4×4 grid, you can choose at most 3 treasures with none being adjacent.

Note: The grid size is provided for convenience, but only the positions of the treasures are used in the selection.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \( T \) representing the number of test cases. Each test case is formatted as follows:

• The first line of each test case contains two integers \( N \) and \( M \), where \( N \) is the grid size (unused in the logic) and \( M \) is the number of treasures.
• The following \( M \) lines each contain two integers \( x \) and \( y \), representing the coordinates of a treasure.

outputFormat

For each test case, print one line to standard output (stdout) containing a single integer — the maximum number of treasures that can be chosen such that no two chosen treasures are adjacent.

## sample

1
4 4
1 1
1 3
2 2
4 4

3

</p>