P9700 [GDCPC 2023] Peg Solitaire

``独立钻石``是一种单人桌游。游戏在 $n$ 行 $m$ 列的棋盘上进行，棋盘上的每一格要么是空格，要么有一枚棋子。一开始，棋盘上共有 $k$ 枚棋子。 在游戏中，玩家可以选择一枚棋子，将它跳过相邻棋子到空格上，并移除被跳过的棋子。具体来说，令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子，玩家可以执行以下四种操作。  给定一个初始的棋盘，求经过任意次操作（包括零次）之后，棋盘上最少能剩余几枚棋子。

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 20$）表示测试数据组数。对于每组测试数据： 第一行输入三个整数 $n$，$m$ 和 $k$（$1 \le n, m \le 6$，$1 \le k \le \min(6, n \times m)$）表示棋盘的行数，列数和初始棋子的数量。 对于接下来 $k$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n$，$1 \le y_i \le m$）表示一开始第 $x_i$ 行第 $y_i$ 列的格子里有一枚棋子。除了这 $k$ 个格子之外，其它格子一开始都是空格。这 $k$ 个格子的位置不会重复。

每组数据输出一行一个整数，表示经过任意次操作（包括零次）之后，棋盘上最少能剩余几枚棋子。 **【样例解释】** 第一组样例数据解释如下。  对于第二组样例数据，由于初始棋盘不存在空格，因此无法进行任何操作。 对于第三组样例数据，由于棋盘不足三格，因此无法进行任何操作。

The first sample test case is explained as follows.  For the second sample test case, as the chessboard does not contain empty cell at the beginning, the player cannot perform any operation. For the third sample test case, as the chessboard has less than three cells, the player cannot perform any operation.