컴퓨터 게임

존(John)과 브루스(Brus)가 컴퓨터로 전략 게임을 하고 있다. 게임은 평평한 지도 위에서 진행된다. 먼저 브루스가 자신의 군대를 배치하면, 존은 다음 규칙에 따라 자기 군대의 전략 지점을 골라야 한다.

• 각 전략 지점은 $|x| + |y| < N$을 만족하는 격자점 $(x, y)$(좌표가 정수인 점)이어야 한다.
• 존은 양의 정수 개수만큼 전략 지점을 고를 수 있다.
• 고른 전략 지점은 모두 서로 달라야 한다.
• 각 전략 지점은 비어 있어야 한다. 즉, 브루스의 군대가 차지하고 있지 않아야 한다.
• 고른 전략 지점들의 모든 쌍은, 오직 고른 다른 전략 지점들만을 거쳐서 서로 연결되어야 한다.

서로 다른 두 격자점 $(x_1, y_1)$과 $(x_2, y_2)$는 $|x_1 - x_2| + |y_1 - y_2| = 1$일 때 서로 인접(직접 연결)한다. 연결은 고른 점들을 통해 추이적으로 이어진다. 즉, 고른 점 $A$와 $B$가 인접하고 $B$와 $C$가 인접하면 $A$와 $C$는 연결되어 있다. 다시 말해, 고른 점들의 집합은 이 인접 관계 아래에서 하나의 연결된 영역을 이루어야 한다.

존이 전략 지점을 고르는 방법의 수를 구하라.

첫 줄에는 정수 $T$, 즉 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 두 정수 $N$과 $M$이 적힌 줄로 시작한다. $N$은 첫 번째 규칙에서 쓰이는 값이고, $M$은 브루스의 군대가 이미 차지한 격자점의 수이다. 이어지는 $M$개의 줄에는 각각 차지된 점의 좌표 $X_k$와 $Y_k$가 주어진다.

제약: $1 \le T \le 74$, $1 \le N \le 7$, $1 \le M \le 225$, $-7 \le X_k, Y_k \le 7$이며, 모든 $(X_k, Y_k)$는 서로 다르다.

각 테스트 케이스마다, 존이 전략 지점을 고르는 방법의 수를 한 줄에 출력한다.