锁定手机的一种方式是使用锁屏图案。要解锁手机，你需要在网格上的某些点之间绘制一条秘密图案，该图案由连接这些点的线段组成。

你的手机图案网格由四行三列的点组成。下图左侧是网格的表示，它可以建模为二维平面，每个点都有 $X$ 和 $Y$ 坐标。例如，左上角的点是 $(1,4)$，右下角的点是 $(3,1)$。右侧的图像是一个有效的图案，它按以下顺序连接了这些点：$(3,4), (2,4), (1,2), (2,1), (2,2), (3,2), (3,1), (1,3)$。

一个有效的图案具有以下属性：

1. 图案可以用它首次接触的点序列来表示（按照绘制图案的顺序）。图案从 $(1,1)$ 到 $(2,2)$ 与从 $(2,2)$ 到 $(1,1)$ 是不同的。

2. 对于图案表示中任意两个连续的点 $A$ 和 $B$，如果连接 $A$ 和 $B$ 的线段经过了其他点，则这些点也必须出现在序列中，且必须出现在 $A$ 和 $B$ 之前，否则该图案无效。例如，一个以 $(3,1)$ 开头然后连接 $(1,3)$ 的图案表示是无效的，因为该线段经过了 $(2,2)$，而 $(2,2)$ 在图案表示中并未出现在 $(3,1)$ 之前。但图案 $(2,2), (3,2), (3,1), (1,3)$ 是有效的，因为 $(2,2)$ 在 $(3,1)$ 之前出现。

3. 在图案表示中，我们不会多次提及同一个点，即使图案通过其他线段再次接触到该点。图案必须从一个点连接到另一个图案之前未接触过的点，在此过程中它可能会经过一些已经出现在图案中的点。

4. 图案的长度是图案中每两个连续点之间的曼哈顿距离之和。两点 $(X_1, Y_1)$ 和 $(X_2, Y_2)$ 之间的曼哈顿距离为 $|X_1 - X_2| + |Y_1 - Y_2|$（其中 $|X|$ 表示 $X$ 的绝对值）。上图中图案的长度为：$1 + 3 + 2 + 1 + 1 + 1 + 4 = 13$。

5. 一个图案必须至少接触两个点。

不幸的是，你忘记了手机的图案，但你记得图案的长度以及一组确定不会被图案接触的点 $S$（不在 $S$ 中的点可能被接触，也可能不被接触）。你决定尝试所有满足你记忆的有效图案。在开始之前，你需要编写一个程序来计算不同有效图案的数量。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100$)。接下来的每个测试用例包含两个整数 $L$ 和 $N$，由空格分隔。$L$ ($1 \le L \le 1,000$) 是图案的长度（如上所述），$N$ ($0 \le N \le 12$) 是你确定不会被图案接触的点数，随后有 $N$ 行，每行包含两个整数 $X$ ($1 \le X \le 3$) 和 $Y$ ($1 \le Y \le 4$)，由空格分隔，表示其中一个确定不会被图案接触的点的坐标。这 $N$ 个点各不相同。

输出格式

对于每个测试用例，如果没有符合你记忆的有效图案，请在一行中打印 "BAD MEMORY"（不含引号），否则打印不同有效图案的数量。

样例

输入 1

3
1 0
2 10
1 1
1 2
1 3
2 1
2 2
2 3
2 4
3 2
3 3
3 4
1 3
1 4
3 4

输出 1

34
BAD MEMORY
24