The Computer Game

John and Brus are playing a strategy game on a computer. The game takes place on a flat map. First Brus deploys his army; then John must choose strategic points for his own army according to the following rules:

• Each strategic point must be a lattice point $(x, y)$ (a point with integer coordinates) such that $|x| + |y| < N$.
• John may choose any positive number of strategic points.
• All chosen strategic points must be distinct.
• Each strategic point must be free, i.e. not occupied by Brus's army.
• Every pair of chosen strategic points must be connected, where the connection may pass only through other chosen strategic points.

Two distinct lattice points $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent (directly connected) when $|x_1 - x_2| + |y_1 - y_2| = 1$. Connection is transitive through chosen points: if chosen points $A$ and $B$ are adjacent and $B$ and $C$ are adjacent, then $A$ and $C$ are connected. In other words, the set of chosen points must form a single connected region under this adjacency.

Count the number of ways for John to choose his strategic points.

The first line contains a single integer $T$, the number of test cases. Each test case begins with a line containing two integers $N$ and $M$: $N$ is the value used in the first rule, and $M$ is the number of lattice points already occupied by Brus's army. Each of the next $M$ lines contains two integers $X_k$ and $Y_k$, the coordinates of one occupied point.

Constraints: $1 \le T \le 74$, $1 \le N \le 7$, $1 \le M \le 225$, $-7 \le X_k, Y_k \le 7$, and all $(X_k, Y_k)$ are distinct.

For each test case, print a single line containing the number of ways for John to choose his strategic points.