시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

루니와 치차리토는 군사 전략 게임을 하고 있다. 이 게임은 평평한 세계 지도를 지도로 사용한다. 게임을 시작하면서 치차리토는 자신의 군대를 배치한다. 

그 다음 루니는 다음과 같은 규칙을 따르면서 전략점을 정한다.

1. 모든 전략점은 |x| + |y| < N을 만족하는 (x, y)위에 있다. (x와 y는 정수)

2. 루니는 전략점을 양수 개수 만큼 고를 수 있다.

3. 모든 전략점 서로 달라야 한다.

4. 각 전략점은 치차리토의 군대가 있는 곳과 겹치면 안된다.

5. 전략점은 모두 서로 연결되어 있어야 한다. (다른 전략점을 통해서 연결되어 있을 수도 있다)

(x1, y1)와 (x2, y2)가 |x1-x2| + |y1-y2| = 1을 만족한다면, 두 점은 연결되어 있는 것이다.

만약, A, B, C가 전략점이고, A와 B가 연결되어 있고, B와 C가 연결되어 있다면, A와 C도 연결되어 있는 것이다.

루니가 전략점을 고를 수 있는 방법의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 M이 공백으로 구분되어져서 주어진다. N은 첫번째 규칙에 나와있는 N이고, M은 치차리토가 배치한 군대의 수이다.

둘째 줄부터 M개의 줄에는 치차리토가 배치한 군대의 좌표 (Xk, Yk)가 주어진다. 이 두 수는 공백으로 구분되어져 있다.

  • 1 ≤ T ≤ 74,
  • 1 ≤ N ≤ 7,
  • 1 ≤ M ≤ 225,
  • -7 ≤ Xk, Yk ≤ 7,
  • 모든 (Xk, Yk) 서로 다르다.

출력

각 테스트 케이스에 대해서 루니가 전략점을 고를 수 있는 방법을 출력한다.

예제 입력

2
2 1
7 7
2 3
0 0
4 -7
7 -4

예제 출력

20
4

힌트