P1110

Pku3901 The Computer Game

Pku3901 The Computer Game

John 和 Brus 正在电脑上进行一场军事战略游戏。游戏在一张平面世界地图上进行。游戏开始时，Brus 会先部署自己的军队，随后 John 需要为自己的军队选择若干战略点。

John 选择的战略点必须满足以下条件：

  • 每个战略点都是满足 ∣x∣+∣y∣<N|x|+|y|<N 的格点 (x,y)(x,y)，其中格点是横、纵坐标均为整数的点；
  • John 必须选择至少一个战略点；
  • 所有战略点互不相同；
  • 所有战略点均未被 Brus 的军队占据；
  • 所有战略点构成一个连通块。

对于两个不同的格点 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2)，若

∣x1−x2∣+∣y1−y2∣=1,|x_1-x_2|+|y_1-y_2|=1,

则称它们直接相连。若能通过其他战略点在两个战略点之间形成一条由直接相连关系组成的路径，则称这两个战略点连通。

请计算 John 选择战略点的方案数。

输入格式

第一行包含一个整数 TT，表示测试用例的数量。

每组测试用例的第一行包含两个以空格分隔的整数 NN 和 MM。其中，NN 表示地图上可选格点需要满足 ∣x∣+∣y∣<N|x|+|y|<N，MM 表示已被 Brus 的军队占据的格点数量。

接下来 MM 行，每行包含两个以空格分隔的整数 XkX_k 和 YkY_k，表示格点 (Xk,Yk)(X_k,Y_k) 已被 Brus 的军队占据。

输出格式

对于每组测试用例，输出一行一个整数，表示 John 选择战略点的方案数。

样例输入

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

样例输出

20
4

数据范围

  • 1≤T≤741\le T\le 74；
  • 1≤N≤71\le N\le 7；
  • 1≤M≤2251\le M\le 225；
  • −7≤Xk,Yk≤7-7\le X_k,Y_k\le 7；
  • 所有给出的格点 (Xk,Yk)(X_k,Y_k) 互不相同。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

20
4