잠금 패턴

휴대폰 잠금 방식 중에 가장 흔한 것이 잠금 패턴이다. 잠금을 풀려면 화면에 놓인 점을 알맞은 순서로 이어서 정해진 모양을 만들어야 한다.

청호의 휴대폰은 4개의 행에 각각 3개의 점이 놓인 잠금 패턴을 쓴다. 점판은 2차원 평면으로 모델링하고, 각 점은 정수 격자점 $(X, Y)$로 나타낸다. 가장 왼쪽 위의 점이 $(1, 4)$, 가장 오른쪽 아래의 점이 $(3, 1)$이다. 즉 $X$는 왼쪽에서 오른쪽으로 1부터 3까지, $Y$는 아래에서 위로 1부터 4까지 커진다.

유효한 패턴을 다음과 같이 정의한다.

• 패턴은 어떤 점을 처음 지나는 순간 그 점의 좌표를 적어 나열한 수열이다. 그려지는 순서대로 점을 적는 것이다. 이때 $(1,1)\ (2,2)$와 $(2,2)\ (1,1)$은 그려지는 순서가 다르므로 서로 다른 패턴이다.
• 패턴에 연달아 나오는 두 점 $A$와 $B$에 대하여, 선분 $AB$ 위에 놓인 다른 점은 모두 그보다 앞서 패턴에 이미 나왔어야 한다. 예를 들어 $(3,1)\ (1,3)$은 유효하지 않은 패턴이지만, $(3,1)\ (2,2)\ (1,3)$이나 $(2,2)\ (3,2)\ (3,1)\ (1,3)$은 유효한 패턴이다.
• 패턴은 같은 점을 두 번 이상 지날 수 있지만, 같은 점을 두 번 이상 적어서는 안 된다. 각 점은 처음 지날 때 한 번만 패턴 안의 점으로 센다.
• 패턴의 길이는 패턴에 연달아 나오는 두 점 사이의 맨해튼 거리를 모두 더한 값이다. 두 점 $(X_1, Y_1)$, $(X_2, Y_2)$의 맨해튼 거리는 $|X_1 - X_2| + |Y_1 - Y_2|$이다.
• 패턴은 점을 최소 두 개 포함해야 한다.

예를 들어 $(3,4)\ (2,4)\ (1,2)\ (2,1)\ (2,2)\ (3,2)\ (3,1)\ (1,3)$은 점 여덟 개를 지나는 유효한 패턴이다.

어느 날 청호는 자기 휴대폰의 잠금 패턴을 잊어버렸다. 그래도 패턴의 길이 $L$과, 패턴이 절대 지나지 않았던 점의 집합 $S$는 기억한다. $S$에 없는 점은 지났을 수도 있고 지나지 않았을 수도 있다.

청호는 기억하는 정보를 바탕으로 모든 경우를 하나하나 시도해 보려 한다. 그 전에 몇 번을 시도해야 하는지 미리 세어 보고 싶다. $S$와 $L$이 주어질 때, 서로 다른 유효한 패턴은 모두 몇 개인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫 줄에 $L$과 $N$이 주어진다. $L$은 패턴의 길이이고, $N$은 청호가 절대 지나지 않았다고 기억하는 점의 개수이다. ($1 \le L \le 1000$, $0 \le N \le 12$)

이어지는 $N$개의 줄에 두 정수 $X$와 $Y$가 주어진다. ($1 \le X \le 3$, $1 \le Y \le 4$) 이는 패턴이 점 $(X, Y)$를 절대 지나지 않았음을 뜻한다.

$N$개의 점은 모두 다르다.

각 테스트 케이스마다 가능한 유효한 패턴의 개수를 한 줄에 출력한다.

가능한 패턴이 하나도 없으면 개수 대신 BAD MEMORY를 출력한다.