Lock Pattern

The most common way to lock a phone is a lock pattern. To unlock it you connect the dots on the screen in the right order so that they draw a fixed shape.

Cheongho's phone uses a lock pattern with 4 rows of 3 dots each. The board is modelled as a 2D plane, and every dot is an integer lattice point $(X, Y)$. The top left dot is $(1, 4)$ and the bottom right dot is $(3, 1)$, so $X$ grows from 1 to 3 going right and $Y$ grows from 1 to 4 going up.

A valid pattern is defined as follows.

• A pattern is the sequence of dot coordinates written down at the moment each dot is first passed, in drawing order. Because the drawing order differs, $(1,1)\ (2,2)$ and $(2,2)\ (1,1)$ are two different patterns.
• For any two consecutive dots $A$ and $B$ in the pattern, every other dot lying on the segment $AB$ must already appear earlier in the pattern. For example $(3,1)\ (1,3)$ is not a valid pattern, while $(3,1)\ (2,2)\ (1,3)$ and $(2,2)\ (3,2)\ (3,1)\ (1,3)$ are valid.
• A pattern may pass the same dot more than once, but no dot may be written down more than once. Each dot counts as a dot of the pattern only the first time it is passed.
• The length of a pattern is the sum of the Manhattan distances between consecutive dots. The Manhattan distance between $(X_1, Y_1)$ and $(X_2, Y_2)$ is $|X_1 - X_2| + |Y_1 - Y_2|$.
• A pattern has to contain at least two dots.

For example, $(3,4)\ (2,4)\ (1,2)\ (2,1)\ (2,2)\ (3,2)\ (3,1)\ (1,3)$ is a valid pattern over eight dots.

One day Cheongho forgot the lock pattern of his phone. He still remembers the length $L$ of the pattern and the set $S$ of dots the pattern never passed. A dot outside $S$ may or may not have been passed.

Cheongho wants to try every remaining case one by one. Before that he wants to count how many tries that will take. Given $S$ and $L$, how many different valid patterns are there?

The first line has the number of test cases $T$. ($1 \le T \le 100$)

The first line of each test case has $L$ and $N$. $L$ is the length of the pattern and $N$ is the number of dots Cheongho remembers as never passed. ($1 \le L \le 1000$, $0 \le N \le 12$)

Each of the next $N$ lines has two integers $X$ and $Y$. ($1 \le X \le 3$, $1 \le Y \le 4$) This means the pattern never passed the dot $(X, Y)$.

The $N$ dots are all different.

For each test case, print the number of possible valid patterns on its own line.

If no pattern is possible at all, print BAD MEMORY instead of a number.